lunchcombo

Problem Description

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 A_i dollars and the ith side dish costing B_i 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.

Input

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.

Output

The output should contain a single integer, the minimum cost, in dollars, Peanut would have to spend on his treat.

Limits

For all subtasks: 1 ≤ M, S ≤ 300 000, 1 ≤ K ≤ MS, 1 ≤ A_i, B_i ≤ 10⁶.

Subtask 1 (35%): 1 ≤ M, S ≤ 1000.

Subtask 2 (24%): 1 ≤ K ≤ 300 000.

Subtask 3 (41%): No additional constraints.

Sample Input

3 3 3
3 2 5
3 2 1

Sample Output

11

Explanation

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.