CF2087F Weapon Upgrade

Monocarp 正在玩一个游戏。游戏分为多个关卡，总共有 $1337$ 个关卡。游戏角色使用一把拥有两种攻击模式的武器：物理攻击和元素攻击。最初，武器的物理攻击力为 $1$，元素攻击力也为 $1$。 在游戏的第 $i$ 个关卡，会按如下顺序发生事件： 1. 如果 $i \le n$，则会出现一只怪物，其物理防御为 $a_i$，元素防御为 $b_i$。否则，不会发生任何事情。 2. Monocarp 可以对剩余的怪物中恰好一只进行攻击。如果该怪物的物理防御不超过角色的物理攻击力，或者元素防御不超过角色的元素攻击力，则该怪物会被击杀。否则，什么也不会发生。 3. 每只存活的怪物会对角色造成 $1$ 点伤害。 每当击杀一只怪物后，Monocarp 可以选择将武器的某一项攻击力提升 $1$。 你的任务是计算 Monocarp 杀死所有怪物所能承受的最小伤害（如果无法杀死所有怪物，则输出 $-1$）。

第一行包含一个整数 $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$。

在第一个样例中，Monocarp 可以按如下方式进行： 第 $1$ 关： - 第 $1$ 只怪物出现； - Monocarp 无法击杀任何怪物； - $1$ 只存活的怪物造成 $1$ 点伤害，总伤害为 $1$。 第 $2$ 关： - 第 $2$ 只怪物出现； - Monocarp 击杀第 $2$ 只怪物（使用元素攻击），并提升物理攻击力； - $1$ 只存活的怪物造成 $1$ 点伤害，总伤害为 $2$。 第 $3$ 关： - 第 $3$ 只怪物出现； - Monocarp 击杀第 $1$ 只怪物（使用物理攻击），并提升元素攻击力； - $1$ 只存活的怪物造成 $1$ 点伤害，总伤害为 $3$。 第 $4$ 关： - 第 $4$ 只怪物出现； - Monocarp 击杀第 $4$ 只怪物（使用元素攻击），并提升元素攻击力； - $1$ 只存活的怪物造成 $1$ 点伤害，总伤害为 $4$。 第 $5$ 关： - Monocarp 击杀第 $3$ 只怪物（使用元素攻击），并提升物理攻击力； - 所有怪物被击杀，总伤害为 $4$。 由 ChatGPT 4.1 翻译