G - ご飯とパン 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

問題文

N 個のライスと M 個のパンがあります。i 番目のライスの美味しさは R_i で、i 番目のパンの美味しさは P_i です。

あなたはこれから K 日間、ライスかパンのいずれか一つを選んで食べることを繰り返します。同じ種類の料理を連続で食べると飽きるので、ライスを二日連続で食べることや、パンを二日連続で食べることは禁じられています。

K 日間の食事が可能か判定し、可能な場合食べる料理のおいしさの総和の最大値を求めてください。

制約

  • 1\leq N,M \leq 1000
  • 1\leq K \leq N+M
  • 1\leq R_i, P_i \leq 1000
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N M K
R_1 \ldots R_N
P_1 \ldots P_M

出力

K 日間の食事が不可能な場合 -1 を出力せよ。可能な場合食べる料理のおいしさの総和の最大値を出力せよ。

入力例 1

3 3 3
2 5 4
3 6 1

出力例 1

15

1 日目に 3 番目のライスを食べ、2 日目に 2 番目のパンを食べ、3 日目に 2 番目のライスを食べることで、食べる料理のおいしさの総和を 15 にできます。

入力例 2

2 4 6
2 4
10 4 4 2

出力例 2

-1

条件を満たす K 日間の食事は不可能です。

Problem Statement

There are N bowls of rice and M slices of bread. The i-th bowl of rice has a deliciousness of R_i, and the i-th slice of bread has a deliciousness of P_i.

For the next K days, you will choose to eat either rice or bread. You will get tired of it if you eat the same dish in a row, so you will never eat rice two days in a row, or eat bread two days in a row.

Determine if this plan is feasible. If it is, find the maximum possible total deliciousness.

Constraints

  • 1\leq N,M \leq 1000
  • 1\leq K \leq N+M
  • 1\leq R_i, P_i \leq 1000
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M K
R_1 \ldots R_N
P_1 \ldots P_M

Output

Print -1 if the plan is infeasible. Otherwise, print the maximum possible total deliciousness of the dishes that you eat.

Sample Input 1

3 3 3
2 5 4
3 6 1

Sample Output 1

15

By eating the third bowl of rice on day 1, the second slice of bread on day 2, and the second bowl of rice on day 3, the total deliciousness will be 15.

Sample Input 2

2 4 6
2 4
10 4 4 2

Sample Output 2

-1

The meal plan for the next K days is infeasible.