C. Dán gỗ
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Thầy Tuấn đang có $$$n$$$ tấm gỗ được đánh số từ $$$1$$$ đến $$$n$$$ có chiều rộng là $$$w_i$$$ chiều cao là $$$h_i$$$. Do sợ tốn tiền mua sơn nên thầy giao nhiệm vụ cho em Bảo phải mua giấy dán cho những tấm gỗ này.

Hiện tại Bảo xác định được trong cửa hàng đang có các miếng dán kích thước cụ thể là $$$R \times C$$$, tức là độ rộng là $$$R$$$ và chiều cao là $$$C$$$. Do đã in banner BKAC nên Bảo không thể xoay chiều được miếng dán.

Biết rằng khi dán, mỗi miếng chỉ có thể nằm gọn trên một tấm gỗ, không có trường hợp dán cho hai hoặc nhiều tấm cùng lúc. Ngoài ra miếng dán không được đổi chiều (xoay miếng dán) và các cạnh miếng dán phải song song với các cạnh tấm gỗ.

Hãy cho biết số miếng dán ít nhất cần để các tấm gỗ đều được dán kín.

Input

Dòng đầu tiên gồm duy nhất một số nguyên dương $$$t$$$ ($$$1 \le t \le 1000$$$) $$$-$$$ số lượng testcases, mỗi testcase gồm ba dòng.

Dòng đầu tiên của mỗi testcase gồm ba số nguyên dương $$$n$$$, $$$R$$$ và $$$C$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le R, C \le 10^{9}$$$) $$$-$$$ số lượng các tấm gỗ và kích thước của miếng dán.

Dòng thứ hai của mỗi testcase gồm $$$n$$$ số nguyên $$$h_1, h_2, \ldots, h_n$$$ ($$$1 \le h_i \le 10^9$$$) $$$-$$$ chiều cao của mỗi tấm gỗ.

Dòng thứ ba của mỗi testcase gồm $$$n$$$ số nguyên $$$w_1, w_2, \ldots, w_n$$$ ($$$1 \le w_i \le 10^9$$$) $$$-$$$ chiều rộng của mỗi tấm gỗ.

Dữ liệu đầu vào bảo đảm tổng $$$n$$$ ở mọi testcase không vượt quá $$$2 \cdot 10^5$$$.

Output

Với mỗi testcase, trên một dòng, in ra số lượng miếng dán cần dùng.

Example
Input
6
2 20 3
12 12
40 100
1 1 1
4
2
8 11 10
10 10 10 10 10 40 50 20
55 11 55 55 22 33 33 44
3 7 8
34 41 39
30 26 9
6 233476014 803143630
6847813 323424606 946007923 753712436 361958625 65047772
410767748 684568549 39950281 892753411 349000147 698300063
2 92526808 107236580
539839331 967415484
606720335 187353153
Output
28
8
53
59
16
72
Note

Ở ví dụ thứ nhất, tấm gỗ đầu tiên cần $$$8$$$ miếng dán và tấm gỗ thứ hai cần $$$20$$$ miếng dán. Tổng số miếng dán cần dùng là $$$28$$$.

Ở ví dụ thứ hai, cần $$$8$$$ miếng dán cho duy nhất một tấm gỗ.

Ở ví dụ thứ tư, các tấm gỗ lần lượt cần $$$25$$$, $$$24$$$ và $$$10$$$ miếng dán, tổng số miếng dán cần dùng là $$$59$$$.