开始: 2023-08-26 00:00:00

0826稠州提高组暑期赛03

结束: 2023-08-26 01:00:00
当前  2025-01-24 17:51:47  类型: IOI  状态: 已经结束 

P1. 小奇挖矿2(mining)
描述

【题目背景】

小奇飞船的钻头开启了无限耐久+精准采集模式!这次它要将原矿运到泛光之源的矿石交易市场,以便为飞船升级无限非概率引擎。

 

【问题描述】

现在有m+1个星球,从左到右标号为0到m,小奇最初在0号星球。

n处矿体,第i处矿体有ai单位原矿,在第bi个星球上。

由于飞船使用的是老式的跳跃引擎,每次只能从第x号星球移动到第x+4号星球或x+7号星球。每到一个星球,小奇会采走该星球上所有的原矿,求小奇能采到的最大原矿数量。

注意,小奇不必最终到达m号星球。


输入

第一行2个整数nm

接下来n行,每行2个整数ai,bi


输出

输出一行一个整数,表示要求的结果


样例

输入

3 13
100 4
10 7
1 11

输出

101
提示

【样例解释】

第一次从0到4,第二次从4到11,总共采到101单位原矿。

 

【数据范围】

对于20%的数据 n=1,m<=10^5

对于40%的数据 n<=15,m<=10^5

对于60%的数据 m<=10^5

对于100%的数据 n<=10^5,m<=10^9,1<=ai<=10^4,1<=bi<=m


提交

题目参数
时间限制 1 秒
内存限制 256 MB
提交