【跳跃】

题目描述

有一只狗,取名叫做 Doge 。
Doge 喜欢跳跃,每次跳跃都是向前跳4或7单位长度。
Doge 有个坏习惯,就是它喜欢吃糖,可以一直吃啊吃啊吃而不被撑死。
一日,主人把 Doge 放在一个很大很大坐标轴上的原点位置。
坐标轴的x正方向上有许多糖果,Doge 眼睛亮了!
每次,Doge 可以跳到它右边4格或右边7格的位置。求它最多能吃到的糖的个数。
当然,如果 Doge 跳累了而想放弃,主人是会把它抱出坐标轴不再吃糖了。

输入格式

第一行为两个正整数 n,m ,分别代表糖的堆数与格子坐标的最大值。
接下来 n 行,每行两个正整数 a[i],b[i],分别代表某堆糖的粒数和位置。

输出格式

输出一个非负整数,最多能吃到的糖的个数。

样例数据 1

输入

3 13
100 4
10 7
1 11

输出

101

备注

【样例解释】
第一次跳 4 格,第二次跳 7 格,总共能吃到 101 粒药。

【数据范围】
对于 20% 的数据,n=1,m≤100,000。
对于 40% 的数据,n≤15,m≤100,000。
对于 60% 的数据,m≤100,000。
对于 100% 的数据,n≤100,000,m≤1,000,000,000,a[i]≤10,000,1≤b[i]≤m。

【提醒】
注意:每个位置不一定只有一堆糖!

对于一段距离L 判断是否可以由4x+7y得来是可以O1判断的(伪扩欧求解部分?) 然而事实上LCR大神证明了18以后的数都是可行的……所以当前状态一定是从前面10个状态以内转移过来的(自己列一下表就知道了),至于哪个状态能转移搜一遍不就好了,才10!

下面是代码:

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*