20220211 - 守纪

a个安静人和b个嘴是租来的人,现在需要从他们中选出n人围成一圈刷题,但如果让嘴是租来的人相邻则所有人都没法刷题。

加入刷题圈的人都会给刷题圈带来荣耀。当然,每个人带来的荣耀可能不同。

求,刷题荣耀最多能达到多少?

刷题圈的荣耀即每个人的带来的荣耀之和。

输入

1行为a,b,n

2行为a+b个整数,前a个表示每个安静的人可以带来的荣耀感;后b个表示每个嘴是租来的人带来的荣耀感。

对于100%的数据:

2 \le a,b \le 10^4

3 \le n \le a+b \le 2×10^5

输出

一个整数,表示可以达到的荣耀之和的最大值。若无法刷题输出-1。

样例

输入

3 6 7
1 3 4 5 4 3 4 3 5

输出

-1

输入

4 6 7
1 3 4 1 5 4 3 4 3 5

输出

23

输入

7 7 7
1 2 3 4 5 6 7 9 8 7 6 5 4 3

输出

46
时间限制 1000 毫秒
内存限制 128 MB
统计
上一题 下一题