Monocarp 正在玩游戏。游戏分为多个阶段,总共有 $$$1337$$$ 阶段。游戏角色使用的武器有两种攻击模式:物理攻击和元素攻击。初始时,武器的物理攻击力为$$$1$$$,元素攻击力也为$$$1$$$。
在游戏的第$$$i$$$阶段,以下事件按顺序发生:
- 如果$$$i \le n$$$,则会出现物理防御力$$$a_i$$$和元素防御力$$$b_i$$$的怪物。否则,什么也不会发生。
- Monocarp 可以射击 正好一个 剩余怪兽的 。如果怪物的物理防御力最多等于角色的物理攻击力 or 怪物的元素防御力最多为角色的元素攻击力,怪物将会被杀死。否则,什么也不会发生。
- 每个幸存的怪物都会对游戏角色造成 $$$1$$$ 伤害。
每次击杀后,Monocarp 可以将武器的其中一项攻击升级 $$$1$$$。
你的任务是计算Monocarp杀死游戏中所有怪物所能获得的最小伤害(或者报告不可能杀死所有怪物)。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 500$$$)。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 500$$$)。
第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le 500$$$)。
输出
打印一个整数——Monocarp 杀死游戏中所有怪物所能获得的最小伤害;如果不可能杀死所有怪物,则打印 -1.
示例
输入复制
42 1 5 35 1 3 2
输出复制
4
输入复制
43 1 5 35 1 3 2
输出复制
-1
输入复制
31 1 11 2 3
输出复制
0
输入复制
86 4 1 2 3 5 1 66 3 2 1 2 3 4 3
输出复制
16
注意
在第一个示例中,Monocarp 可以按如下方式进行:
$$$1$$$-st 阶段:
- $$$1$$$-st 怪物出现;
- Monocarp 无法杀死任何怪物;
- $$$1$$$ 活怪物造成 $$$1$$$ 伤害,因此 Monocarp 受到的总伤害为 $$$1$$$。
- $$$2$$$-第一个怪物出现;
- Monocarp 杀死 $$$2$$$-nd 怪物(使用元素攻击)并升级物理伤害;
- $$$1$$$ 活怪物造成 $$$1$$$ 伤害,因此 Monocarp 受到的总伤害为 $$$2$$$。
- $$$3$$$-第一个怪物出现;
- Monocarp 杀死 $$$1$$$-st 怪物(使用物理攻击)并升级元素伤害;
- $$$1$$$ 活着的怪物造成 $$$1$$$ 伤害,因此 Monocarp 受到的总伤害为 $$$3$$$。
- 第$$$4$$$个怪物出现;
- Monocarp杀死$$$4$$$个怪物(使用元素攻击)并升级元素伤害;
- $$$1$$$ 活着的怪物造成 $$$1$$$ 伤害,因此 Monocarp 受到的总伤害为 $$$4$$$。
- Monocarp 杀死 $$$3$$$-rd 怪物(使用元素攻击)并升级物理伤害;
- 所有怪物均被杀死,Monocarp 受到的总伤害为 $$$4$$$。