← 返回题目列表

Codeforces · 2087/F

F. 武器升级

中文机器翻译题面 查看原题

Monocarp 正在玩游戏。游戏分为多个阶段,总共有 $$$1337$$$ 阶段。游戏角色使用的武器有两种攻击模式:物理攻击和元素攻击。初始时,武器的物理攻击力为$$$1$$$,元素攻击力也为$$$1$$$。

在游戏的第$$$i$$$阶段,以下事件按顺序发生:

  1. 如果$$$i \le n$$$,则会出现物理防御力$$$a_i$$$和元素防御力$$$b_i$$$的怪物。否则,什么也不会发生。
  2. Monocarp 可以射击 正好一个 剩余怪兽的 。如果怪物的物理防御力最多等于角色的物理攻击力 or 怪物的元素防御力最多为角色的元素攻击力,怪物将会被杀死。否则,什么也不会发生。
  3. 每个幸存的怪物都会对游戏角色造成 $$$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.

示例

输入
复制

4
2 1 5 3
5 1 3 2

输出
复制

4

输入
复制

4
3 1 5 3
5 1 3 2

输出
复制

-1

输入
复制

3
1 1 1
1 2 3

输出
复制

0

输入
复制

8
6 4 1 2 3 5 1 6
6 3 2 1 2 3 4 3

输出
复制

16

注意

在第一个示例中,Monocarp 可以按如下方式进行:

$$$1$$$-st 阶段:

  • $$$1$$$-st 怪物出现;
  • Monocarp 无法杀死任何怪物;
  • $$$1$$$ 活怪物造成 $$$1$$$ 伤害,因此 Monocarp 受到的总伤害为 $$$1$$$。
$$$2$$$-第二阶段:
  • $$$2$$$-第一个怪物出现;
  • Monocarp 杀死 $$$2$$$-nd 怪物(使用元素攻击)并升级物理伤害;
  • $$$1$$$ 活怪物造成 $$$1$$$ 伤害,因此 Monocarp 受到的总伤害为 $$$2$$$。
$$$3$$$-rd阶段:
  • $$$3$$$-第一个怪物出现;
  • Monocarp 杀死 $$$1$$$-st 怪物(使用物理攻击)并升级元素伤害;
  • $$$1$$$ 活着的怪物造成 $$$1$$$ 伤害,因此 Monocarp 受到的总伤害为 $$$3$$$。
$$$4$$$-第阶段:
  • 第$$$4$$$个怪物出现;
  • Monocarp杀死$$$4$$$个怪物(使用元素攻击)并升级元素伤害;
  • $$$1$$$ 活着的怪物造成 $$$1$$$ 伤害,因此 Monocarp 受到的总伤害为 $$$4$$$。
$$$5$$$-第阶段:
  • Monocarp 杀死 $$$3$$$-rd 怪物(使用元素攻击)并升级物理伤害;
  • 所有怪物均被杀死,Monocarp 受到的总伤害为 $$$4$$$。