Mảng khác biệt
Xem PDFPetya có một mảng \(a_i\) gồm \(n\) số nguyên. Anh trai của anh ấy, Vasya, ghen tị và quyết định tạo ra một mảng của riêng mình gồm \(n\) số nguyên.
Để làm điều này, anh ta tìm thấy \(m\) số nguyên \(b_i (m≥n)\), và bây giờ anh ta muốn chọn \(n\) số nguyên trong số chúng và sắp xếp chúng theo một thứ tự cụ thể để có được một mảng \(c_i\) có độ dài \(n\).
Để tránh giống với anh trai mình, Vasya muốn làm cho mảng của mình khác biệt nhất có thể so với mảng của Petya. Cụ thể, anh ấy muốn tổng chênh lệch \(D=\sum_{i=1}^{n}|a_i−c_i|\) là lớn nhất có thể.
Hãy giúp Vasya tìm ra chênh lệch lớn nhất \(D\) mà anh ta có thể đạt được.
Dữ liệu vào
Mỗi test bao gồm nhiều test case. Dòng đầu tiên chứa một số nguyên duy nhất \(t (1≤t≤100)\) — số lượng test case. Tiếp theo là mô tả của các test case.
Dòng đầu tiên của mỗi test case chứa hai số nguyên \(n\) và \(m\) \((1≤n≤m≤2.10^5)\).
Dòng thứ hai của mỗi test case chứa \(n\) số nguyên \(a_i\) \((1≤a_i≤10^9)\). Dòng thứ ba của mỗi test case chứa \(m\) số nguyên \(b_i (1≤b_i≤10^9)\).
Đảm bảo rằng trong mỗi test case, tổng \(m\) không vượt quá \(2.10^5\).
Dữ liệu ra
Đối với mỗi test case , đầu ra là một số nguyên duy nhất — chênh lệch tổng lớn nhất \(D\) mà có thể đạt được.
Sample
Input
9
4 6
6 1 2 4
3 5 1 7 2 3
3 4
1 1 1
1 1 1 1
5 5
1 2 3 4 5
1 2 3 4 5
2 6
5 8
8 7 5 8 2 10
2 2
4 1
9 6
4 6
8 10 6 4
3 10 6 1 8 9
3 5
6 5 2
1 7 9 7 2
5 5
9 10 6 3 7
5 9 2 3 9
1 6
3
2 7 10 1 1 5
Output
16
0
12
11
10
23
15
25
7
Giải thích
Trong ví dụ đầu tiên, Vasya có thể, ví dụ, tạo ra mảng \((1,5,7,2)\). Sau đó, tổng chênh lệch sẽ là \(D=|6−1|+|1−5|+|2−7|+|4−2|=5+4+5+2=16\).
Trong ví dụ thứ hai, tất cả các số nguyên có sẵn cho Vasya đều bằng nhau và anh ta chỉ có thể tạo ra mảng \((1,1,1)\), với chênh lệch \(D=0\).
Trong ví dụ thứ ba, Vasya có thể, ví dụ, tạo ra mảng \((5,4,3,2,1)\). Sau đó, tổng chênh lệch sẽ là \(D=|1−5|+|2−4|+|3−3|+|4−2|+|5−1|=4+2+0+2+4=12\).
Bình luận