该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

众所周知，”胖头鱼战士“是知名二字游戏《原鱼》中的一名双手键角色，顾名思义，就是双手各拿一个键盘当做武器的角色，为了展现出新角色的独特之处，同时让玩家有更好的氪金游戏体验，游戏策划胖头鱼专门为该角色设置了两类武器：左手键和右手键。

每一把武器都有独特的效果，为了便于玩家进行消费选择，一个合理的武器展示界面是必不可少的。为此，胖头鱼设计了一个相当科学的展示方法，展示界面可以看作是一个宽度为 $w$ 的网格，高度是无限的，因为界面可以通过鼠标滚轮上下滑动。展示界面又分为左右两边，分别用于展示左手键和右手键，两个区域的宽度可以由玩家自行调整，但是总和必须是 $w$ 。

因为武器是键盘，所以在展示界面中，所有武器的高度均为 $1$ ，但是宽度可能各不相同。两类武器都会按照给定顺序从第 $1$ 行开始由左向右逐个陈列，由于展示区域的宽度是有限的，所以当某个武器无法在当前行完整展示时，就会从下一行开始继续按照上述规则进行陈列。由此可知，两边展示区域的宽度均不能小于对应种类武器的最大宽度。

胖头鱼现在有 $n$ 把左手键，宽度分别为 $a_1, \dots, a_n$ ，还有 $m$ 把右手键，宽度分别为 $b_1, \dots, b_m$ 。考虑到在展示时，如果有一边的区域很高，而另一边很矮，会显得非常不美观，所以现在胖头鱼想知道，如何设置两边区域的宽度，才能使得两个区域高度的较大值最小。显然，这个简单的任务很适合新招的临时工拿来练手，所以请你尽快完成吧。

输入格式

第一行包含三个整数 $n$ 、 $m$ 和 $w$ ，表示有 $n$ 把左手键， $m$ 把右手键，展示界面的宽度为 $w$ 。

第二行包含 $n$ 个整数 $a_i$ ，按顺序给出每把左手键的宽度。

第三行包含 $m$ 个整数 $b_i$ ，按顺序给出每把右手键的宽度。

输出格式

输出一个整数，表示两个展示区域高度较大值的最小值。

数据样例

【样例 1 输入】

存放在 sample/weapon 目录下的 weapon1.in 文件中。

3 4 10
8 1 1
2 2 2 2

【样例 1 输出】

存放在 sample/weapon 目录下的 weapon1.out 文件中。

4

【样例 1 解释】

只能将左边区域的宽度设置成 $8$ ，此时右边区域的宽度为 $2$ 。

左边区域的高度为 $2$ ，右边区域的高度为 $4$ ，因此答案为 $\max(2, 4) = 4$ 。

【样例 2 输入】

存放在 sample/weapon 目录下的 weapon2.in 文件中。

4 4 10
5 2 2 1
2 2 2 2

【样例 2 输出】

存放在 sample/weapon 目录下的 weapon2.out 文件中。

2

【样例 2 解释】

将左边区域的宽度设置成 $6$ 是最佳方案，此时右边区域的宽度为 $4$ ，左右区域的高度均为 $2$ 。

【样例 3 、 4 和 5】

存放在 sample/weapon 目录下的 weapon3.in 和 weapon3.out 、 weapon4.in 和 weapon4.out 、 weapon5.in 和 weapon5.out 文件中。

weapon.zip

数据说明

对于所有测试点，满足 $0 ≤ n, m ≤ 2 \times 10^5$ 、 $1 ≤ a_i, b_i, w ≤ 10^9$ ， $\max(a_i) + \max(b_i) ≤ w$ 。

子任务及其特殊属性如下：

• 子任务 $1$ 占 $10\%$ 的分数，满足 $a_i = b_i = 1$ ，表示所有武器的宽度均为 $1$ 。
• 子任务 $2$ 占 $15\%$ 的分数，满足 $n, m ≤ 20$ ，表示武器数量极少。
• 子任务 $3$ 占 $20\%$ 的分数，满足 $n, m ≤ 200$ ，表示武器的数量很少。
• 子任务 $4$ 占 $10\%$ 的分数，满足 $m = 0$ ，表示没有右手键。
• 子任务 $5$ 占 $15\%$ 的分数，满足 $w ≤ 100$ ，表示总宽度很小。
• 子任务 $6$ 占 $30\%$ 的分数，没有特殊属性。