
ZOJ Problem Set  4043
Do you know UTAU? It's a Japanese singing synthesizer application created by Ameya/Ayame which allows users to control some virtual singers to perform their own songs. Everybody is also welcomed to upload their own voicebanks (and optionally design a virtual character for their voices) to become a virtual singer themselves! As we know, everybody's voice is unique and has its own characteristics, so one has to be really careful when it comes to selecting a group of virtual singers to perform a song. There are currently $n$ virtual singers in UTAU and the characteristic of the $i$th virtual singer is denoted as $a_i$. To perform a song, one needs to select $m$ virtual singers and assign them into different positions. The best characteristic of the singer in the $i$th position is denoted as $b_i$. Two groups of virtual singers performing the same song. Which group do you prefer? Of course, one cannot always select and arrange a group of virtual singers perfectly as the resource of the software is limited. Let's say one has selected a group of $m$ virtual singers from the software and has assigned the singers into their positions so that the singer in the $i$th position has a characteristic of $c_i$, then the disharmony of the group can be calculated as $$D = \sum_{i=1}^m c_ib_i$$ where $D$ is the disharmony of the group. Please select a group of $m$ virtual singers from the $n$ provided singers and arrange them properly, so that the disharmony is as small as possible. Note that each singer can be selected at most once and can only be arranged into one position! InputThere are multiple test cases. The first line of the input is an integer $T$, indicating the number of test cases. For each test case: The first line contains two integers $n$ and $m$ ($1 \le m \le n \le 10^5$), indicating the number of provided virtual singers and the number of singers needed to perform a song. The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$), indicating the characteristic of the $i$th provided singer. The third line contains $m$ integers $b_1, b_2, \dots, b_m$ ($1 \le b_i \le 10^9$), indicating the best characteristic of the singer in the $i$th position. The sum of $n$ in all test cases is about $10^6$. OutputFor each test case output one line containing one integer, indicating the smallest possible disharmony. Sample Input6 6 3 2 3 7 9 4 5 4 1 8 3 2 3 8 5 6 4 4 2 3 6 5 6 5 5 3 3 1 10 100 1000 10000 100000 5 1 10 20 30 40 50 33 5 3 1 1 1 1 1 1 1 1 Sample Output2 2 1 110889 3 0 HintFor the first sample test case, we should select the 1st, 3rd and 5th singer and assign the 1st singer to the 2nd position, the 3rd singer to the 3rd position and the 5th singer to the 1st position. The answer is 4  4 + 2  1 + 7  8 = 2. For the second sample test case, we should select the 1st and 3rd singer and assign the 1st singer to the 2nd position and the 3rd singer to the 1st position. The answer is 5  6 + 3  4 = 2. For the third sample test case, we should select the 2nd and 3rd singer and assign the 2nd singer to the 1st position and the 3rd singer to the 2nd position. The answer is 6  5 + 5  5 = 1. For the fifth sample test case, we should select the 3rd singer and assign him to the 1st position. The answer is 30  33 = 3. Author: WENG, Caizhi Source: ZOJ Monthly, June 2018 