A restaurant is offering a special lunch combo, consisting of a single main course and a side dish. There are a total of M main courses and S sides, with the ith main course costing Ai dollars and the ith side dish costing Bi dollars. The cost of a particular lunch combo is simply the sum of the cost of the main course and side dish.
Peanut wants to treat a total of K of his friends to a lunch combo each, but he wishes that no two friends receive the same combo. Two combos are considered to be different if either the main course or side dish (or both) differs. Help Peanut figure out the minimum cost, in dollars, he would have to spend on this treat.
The first line of input will contain three integers, M, S and K.
The second line of input will contain M integers, representing the array A.
The third line of input will contain S integers, representing the array B.
The output should contain a single integer, the minimum cost, in dollars, Peanut would have to spend on his treat.
For all subtasks: 1 ≤ M, S ≤ 300 000, 1 ≤ K ≤ MS, 1 ≤ Ai, Bi ≤ 106.
Subtask 1 (35%): 1 ≤ M, S ≤ 1000.
Subtask 2 (24%): 1 ≤ K ≤ 300 000.
Subtask 3 (41%): No additional constraints.
3 3 3
3 2 5
3 2 1
The first friend would receive main 2 and side 3 ($2+$1 = $3). The second friend would receive main 2 and side 2 ($2+$2 = $4). The third friend would receive main 1 and side 3 ($3+$1=$4). The total cost would therefore be $3+$4+$4=$11.