原题：streaming_3 noip模拟赛 4和7

「题目背景」

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

「问题描述」

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

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

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

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

「输入格式」

第一行2个整数n，m。

接下来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

题解

对于20%的数据，n=1。只需判断这个星球位置是否能拆分成4和7的和。

可以简单递推，枚举求得。

打表的话可以发现，只有1 2 3 5 6 9 10 13 17不能拆。

对于40%的数据，n很小。可以2^n枚举去哪些星球，然后用上面的方法判定一个星球能否到下一个星球。

对于60%的数据，m比较小。设x[i]为i号星球的原矿数，f[i]为到i号星球能获得的最大原矿数，则f[i]=max{f[i-4],f[i-7]}+x[i]。

对于100%的数据，m很大。

1.将所有矿物排序，f[i]为到第i个矿体能获得的最大原矿数，那么f[i]=max{f[j]}+x[i]，其中，i-j满足能拆分成4和7。

这样dp需要n^2的复杂度，但是我们发现，相距超过17的一定可达，那么不超过17的范围内暴力，超过17的取个最大值即可，复杂度O(n)

2.可以把相邻的星球距离超过17的压缩成18，按照60%的做法dp