Có \(n\) máy tính và \(m\) tháp ở các vị trí phân biệt trên một đường thẳng. Hãy ghép mọi máy tính thành các cặp khác nhau. Một dây nối hai máy có thể ghé bất kỳ dãy tháp nào theo thứ tự tùy ý, kể cả không ghé tháp nào; dây có thể đi ngang qua một tháp mà không ghé tháp đó.

Nếu dây đi từ vị trí \(a\) qua các tháp \(x_1,\ldots,x_k\) đến \(b\), độ dài là \(|a-x_1|+|x_1-x_2|+\cdots+|x_k-b|\). Điểm của dây là \(f\cdot u-l\), với \(u\) là số tháp khác nhau mà dây ghé. Các dây khác nhau có thể cùng ghé một tháp. Hãy tối đa tổng điểm.

Dữ liệu vào

Dòng đầu chứa \(T\). Mỗi test gồm ba dòng: \(n,m,f\); \(n\) vị trí máy tính \(a_1,\ldots,a_n\); và \(m\) vị trí tháp \(b_1,\ldots,b_m\).

Dữ liệu ra

In \(T\) số nguyên, mỗi số là tổng điểm lớn nhất của một test.

Ràng buộc

• \(1\le T\le10^4\). Gọi \(N,M\) lần lượt là tổng các \(n,m\) qua mọi test: \(1\le N,M\le2\cdot10^5\).
• \(0\le f\le10^9\), \(n\) chẵn.
• \(1\le a_i,b_i\le10^9\); mọi vị trí trong một test là phân biệt.

Phân nhóm

1. \(5\) điểm: \(N\le5000\), \(m=1\).
2. \(10\) điểm: \(T\le20\), \(n\le10\), \(m\le100\).
3. \(27\) điểm: \(N,M\le5000\).
4. \(21\) điểm: \(N\le5000\).
5. \(37\) điểm: không có ràng buộc thêm.

Ví dụ

4
2 1 100
1 10
11
4 1 10
2 4 6 8
20
4 1 10
2 4 6 8
5
6 3 10
2 13 4 8 6 10
5 1 9

89
-4
12
51

Nguồn

CEOI 2026 - Ngày 2, bài Towers.

Đề bài, dữ liệu kiểm thử và lời giải tham khảo được lấy từ nguồn CEOI 2026 chính thức.