题目内容

多多鸡在挑战强大的 $BOSS$，他有$n$个技能，每个技能具有：

• 伤害值：释放一次造成的伤害
• 冷却时间：释放后必须等待的时间（从释放开始计算）

注意：一旦释放某个技能，就必须周期性地持续释放它！

具体规则如下：

• 你可以在 $t$ 秒内使用 $1$ 次初始释放一个技能：
• 每次释放耗时 $1$ 秒，期间不能释放其他技能
• 之后必须在 $t + c, t + 2c ,t+3c, ...$ 持续释放该技能（只要不超时），其中 $c$ 为冷却时间。如果 $c$ 小于 $1s$，因为有释放时间，则两次释放之间仍然必须大于等于 $1s$。
• 不能中途切换技能，也不能组合多个技能
• 同一时间只能释放一个技能（所以不同技能的时间方案互斥）

战斗从时刻 $0$ 开始，持续 $T$ 秒，你只能选择一个技能和一个起始时间（起始时间为 $0$ 到 $T$ 之间的正整数），进行周期性释放。

目标：选择一个技能和一个起始时间，使得在 $[0,T)$ 时间内造成的总伤害最大。

输入描述

第一行：一个整数 $T$，表示总战斗时长（$1 \le T \le 1000$）

第二行：$N$ 个整数，表示每个技能的伤害值 $damage[i]$（$1 \le n \le 10$，$1 \le damage[i] \le 10^9$）

第三行：$N$ 个整数表示每个技能的冷却时间 $cooldown[i]$（$1 \le n \le 10$，$0 \le cooldown[i] \le 1000$）

其中，第二第三行的数据个数一定是相等的。

输出描述

总伤害最大值。

样例1

输入

10
50
3

输出

200

说明

技能只有 $1$ 个，伤害 $50$，冷却时间 $3$。

• 起始时间 $t=0$：可在 $0,3,6,9$ 释放 $→ 4$ 次
• 总伤害 $= 50 × 4 = 200$
• 其他起始时间不会更多
• 输出 $200$

样例2

输入

5
30
2

输出

90

说明

• $t=0$：$0,2,4 → 3次 → 3×30 = 90$
• $t=1$：$1,3 → 2次 → 2×30 = 60$
• 最大是 $90$