小慕负责公司的云短信采购，为庆祝国庆，平台推出了充值优惠活动。 现在给出小慕的，以及，求他最多能获得的短信总条数。
提示：带虚线的词点一下有通俗解释。
输入描述
<div class="ace-line ace-line old-record-id-GPr3d2kyWoWKIaxIXNpcwmBunjd" style="white-space:pre-wrap;"> 第一行客户预算 <code>M</code>，其中 <code>0 <= M <= 1000000</code> </div> <div class="ace-line ace-line old-record-id-AsdwdRabnooS75xSHUEc6bV9nYl" style="white-space:pre-wrap;"> 第二行给出售价表，<code>P1, P2, …, Pn</code>, 其中 <code>Pi</code> 为充值 <code>i</code> 元获得的短信条数。 </div> <div class="ace-line ace-line old-record-id-TIObdJDBRogxvAxWKv1cyqHwnwL" style="white-space:pre-wrap;"> <code>1 <= Pi <= 1000</code>， <code>1 <= n <= 100</code> </div>
输出描述
<span style="white-space:pre-wrap;"> 最多获得的短信条数</span>
示例
示例 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
时间限制 1000 ms · 内存限制 128 MB