$N$ 家银行提供各自的一年期存款活动。对于银行 $i$，$(v_i, w_i)$ 分别表示其存款活动的年利息和存款限额。当储户选择银行 $i$ 的活动时，必须存入金额为 $w_i$ 的资金，存期为一年。注意，每位储户对每项活动只能选择一次。如果储户拥有的现金为 $C$，他/她最多能获得的存款利息是多少？

输入格式

第一行是一个整数，表示现金 $C$。第二行包含 $N$ 个整数，其中第 $i$ 个整数表示 $v_i$。第三行也包含 $N$ 个整数，其中第 $i$ 个整数表示 $w_i$。注意，相邻整数之间用空格隔开。

输出格式

一个整数，表示储户能获得的最大存款利息。如果无法获得任何存款利息，请输出 0。

数据范围

• $1 \le N \le 100$
• $1 \le C \le 1,000$（单位：万元）
• $1 \le v_i \le 540$（单位：千元）
• $1 \le w_i \le 300$（单位：万元）

样例

输入 1

100
10 5 15 7
20 30 50 70

输出 1

30

输入 2

500
72 2 2 10 12 10 10 17 13 15
120 10 5 20 25 100 80 300 50 100

输出 2

144

输入 3

5
1 2
10 20

输出 3

0