Problem Description

$ A $ and $ B $ are enjoying the DDPC Special Buffet at the DISCO presents Discovery Channel Programming Contest 2016 Finals. $ A $ has $ N $ dishes on his tray, and $ B $ has $ M $ dishes on his tray. The deliciousness of the $ i $-th dish on $ A $'s tray is represented by $ A_i $, and the deliciousness of the $ j $-th dish on $ B $'s tray is represented by $ B_j $.

As they are very good friends, they decided to perform exactly $ K $ exchanges of one dish from $ A $'s tray with one dish from $ B $'s tray to enjoy their lunch more. When the total deliciousness of the dishes on $ A $'s tray is $ a $ and the total deliciousness of the dishes on $ B $'s tray is $ b $, their happiness is represented by $a \times b$.

Find the maximum possible happiness after performing $ K $ exchanges.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ K $ $ A_1 $ $ A_2 $ … $ A_N $ $ B_1 $ $ B_2 $ … $ B_M $

• The first line contains integers $N,\ M\ (1 \leq N, M \leq 55)$ representing the number of dishes $ A $ and $ B $ have, and the number of exchanges $K\ (1 \leq K \leq 999)$.
• The second line contains integers $A_i\ (0 \leq A_i \leq 22,222)$ representing the deliciousness of the $ i $-th dish on $ A $'s tray, separated by spaces.
• The third line contains integers $B_j\ (0 \leq B_j \leq 22,222)$ representing the deliciousness of the $ j $-th dish on $ B $'s tray, separated by spaces.

Output Format

Output the maximum possible happiness of the two in one line. Do not forget the newline at the end.

Sample Input and Output

Sample Input #1

3 2 1
2 2 3
3 2

Sample Output #1

36

Sample Input #2

3 2 2
2 2 2
3 3

Sample Output #2

36

Notes/Hints

Partial Points

This problem has partial points:

• $ 10 $ points are awarded for solving the dataset where $ K = 1 $.
• Additional $ 20 $ points are awarded for solving the dataset where $0 \leq A_i, B_j \leq 55$.
• Additional $ 70 $ points are awarded for solving the dataset without additional constraints, totaling $ 100 $ points.

Sample Explanation 1

• Exchanging the dish with deliciousness $ 3 $ from $ A $'s tray with the dish with deliciousness $ 2 $ from $ B $'s tray results in a happiness of $ 36 $, which is the maximum happiness.

Sample Explanation 2

• In the first exchange, swap the dish with deliciousness $ 2 $ from $ A $'s tray with the dish with deliciousness $ 3 $ from $ B $'s tray. In the second exchange, swap the dish with deliciousness $ 3 $ from $ A $'s tray with the dish with deliciousness $ 2 $ from $ B $'s tray. This results in a happiness of $ 36 $, which is the maximum happiness.

见题面 Input 部分

见题面 Output 部分