问题陈述
有 N 碗米饭和 M 面包片。 的 i第碗米饭的美味 R_i,以及 i第 片面包的美味程度为 P_i.
对于下一个 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
输出
打印 -1 如果计划不可行。 否则,打印您吃的菜肴的最大可能总美味。
示例输入 1
3 3 3 2 5 4 3 6 1
示例输出 1
15
吃当天的第三碗饭 1,当天的第二片面包 2,还有当天的第二碗米饭 3,总美味将是 15.
示例输入 2
2 4 6 2 4 10 4 4 2
示例输出 2
-1
接下来的膳食计划 K 天是不可行的。