#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

## 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 *i*th main course costing *A _{i}* dollars and the

*i*th side dish costing

*B*dollars. The cost of a particular lunch combo is simply the sum of the cost of the main course and side dish.

_{i}
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^{6}.

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.

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 35 | 11 | 1s | 256MB | Minimum |

2 | 24 | 21 | 1s | 256MB | Minimum |

3 | 41 | 31 | 1s | 256MB | Minimum |

4 | 0 | 1 | 1s | 256MB | Minimum |

### Judge Compile Command

g++-8 ans.cpp -o lunchcombo -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512