Sau khi về nhất trong cuộc thi Coding của admin __BruteForce__, anh chàng BRUH kiếm được một số tiền rất lớn do đó anh quyết định xây lại bức tường nhà mình. Vì căn nhà đã được xây dựng từ rất lâu nên các bức tường bị hư hại nặng nề, chiều cao của các cột trụ không còn được bằng nhau.

Tường nhà BRUH có \(n\) cột trụ có chiều cao tương ứng là \(h_1,\ h_2,\ldots,\ h_n\), để bức tường trở nên đẹp thì chiều cao của các cây cột phải bằng nhau. Điều này có thể được thực hiện bằng việc loại bỏ một số viên gạch từ các cây cột, hoặc xây thêm vào một số viên gạch. Chi phí xây dựng của mỗi cây cột là khác nhau, đơn giá đối với cột thứ \(i\) sẽ là \(c_i\). Tổng chi phí để tu sửa một cây cột bất kỳ sẽ bằng số lượng viên gạch cần thêm vào / bỏ đi nhân với đơn giá của cây cột đó.

Tìm chi phí thấp nhất để khiến bức tường trở nên đẹp như ý muốn của BRUH, hay nói cách khác là tìm chi phí thấp nhất để \(h_1=h_2=\ldots=h_n=k\) (với \(k\) là một số nguyên dương bất kỳ).

Input

• Dòng đầu tiên chứa số nguyên dương \(T\) - số bộ dữ liệu;
• Tiếp theo là \(3\times T\) dòng, mỗi \(3\) dòng thể hiện một bộ dữ liệu:
  • Dòng đầu của mỗi bộ dữ liệu chứa số nguyên dương \(n\) - số cột trụ của dãy tường nhà BRUH;
  • Dòng thứ hai chứa \(n\) số nguyên dương \(h_1,\ h_2,\ldots,\ h_n\) - chiều cao của các cây cột;
  • Dòng thứ ba chứa \(n\) số nguyên dương \(c_1,\ c_2,\ldots,\ c_n\) - chi phí để xây thêm / bỏ đi các viên gạch đối với từng cây cột.

Output

• Gồm \(T\) dòng, mỗi dòng in ra chi phí tối thiểu của bộ dữ liệu tương ứng.

Ví dụ

Sample input

1
3
1 2 3
10 100 1000

Sample output

120

Ràng buộc

• \(T\leq15,\ n\leq10^4\);
• \(0\leq h_i,\ c_i\leq10^4,\ \forall i\in [1..n]\)
• Có \(20\%\) số test tương ứng với \(20\%\) số điểm có \(c_1=c_2=\ldots=c_n\) trong mọi bộ dữ liệu.