题目描述

你正在面对一个冒险游戏的最终 Boss。他的生命值为 $h$ 。你的角色有 $n$ 种技能， 第 $i$ 种技能可以对 Boss 造成 $a_i$ 点伤害但需要 $c_i$ 秒冷却。你的技能冷却完毕时你会立刻使用该技能。也就是说，如果你在第 $x$ 秒使用技能，那么你下次使用该技能的时间是第 $x + c_i$ 秒。

最开始所有技能都已经冷却完毕。你需要多少秒才能打败Boss？（如果 Boss 的生命降低到 $0$ 或以下，他就被击败了）

输入格式

第一行输入两个整数 $h$ 和 $n$ 。

第二行输入 $n$ 个整数 $a_1, a_2, ..., a_n$ 。

第二行输入 $n$ 个整数 $c_1, c_2, ..., c_n$ 。

输出格式

输出一个整数，表示答案。

3 2
2 1
2 1

1

50 3
5 6 7
5 6 7

15

提示

$1 \leq n, h \leq 10^5$ ，$1\leq a_i,c_i \leq 2 \cdot 10^5$ 。