云短信平台优惠活动
题目描述
某云短信厂商, 为庆祝国庆, 推出充值优惠活动. 现在给出客户预算, 和优惠售价序列, 求最多可获得的短信总条数.
输入描述
- 第一行客户预算M, 其中 0 ≤ M ≤ 10^6
- 第二行给出售价表, P1, P2, … Pn, 其中 1 ≤ n ≤ 100
- Pi为充值 i 元获得的短信条数. 1 ≤ Pi ≤ 1000 , 1 ≤ n ≤ 100
输出描述
最多获得的短信条数.
示例1
输入:
6
10 20 30 40 60
输出:
70
说明: 分两次充值最优, 1元, 5元各充一次, 总条数 10 + 60 = 70.
示例2
输入:
15
10 20 30 40 60 60 70 80 90 150
输出:
210
说明: 分两次充值最优, 10元, 5元各充一次, 总条数 150 + 60 = 210.