牛牛打开了一个有趣的游戏。在游戏中，灵石是一种非常重要的资源。每位玩家每天有且仅有一次采集的机会。灵石会在许多浮岛上刷新，每个浮岛上灵石刷新数量可能不同。这些浮岛之间通过传送法阵相连，激活每个岛屿上的传送法阵花费的灵石数量也不同。玩家可以耗费 \(m_i\) 块灵石从任意一个其他浮岛或初始平台前往第 \(i\) 个浮岛。采集完毕后玩家可以从任何浮岛直接退出地图。现在，牛牛手中有着 \(K\) 块灵石，他想知道自己今天采集结束后最多能拥有多少块灵石。牛牛只能在周末玩一小时游戏，他希望你能编写一个程序帮他及时算出来。
第一行两个正整数 \(N,K\) 分别表示浮岛的数量和牛牛手中初始的灵石数量。
接下来 \(N\) 行，每行两个正整数\(k_i,m_i\)，第 \(i\) 行的正整数 \(k_i\) 表示第 \(i\) 个浮岛上今日刷新的灵石数量, \(m_i\) 表示传送到第 \(i\) 个浮岛所需的灵石数量。
一个正整数，表示牛牛今天采集后最多能拥有的灵石数量。
对于 \(30\%\) 的数据，满足 \(k_i>m_i\)对于 \(100\%\) 的数据，满足\(0 < N,K\leq10^5,0<ki,mi≤10^9\)保证答案在int范围内。
贪心
对于没有收益的岛屿肯定是不去的，为使收益尽可能大，应该尽量把那些能去的且有收益的岛屿去完，才有可能去那些更难去的岛屿~
小 \(\text{B}\) 很喜欢排列，这次他有一个长为 \({n}\) 的排列 \(a_1,a_2,\cdots,a_n\)。由于他音游玩多了，所以他想让排列也跳跃起来。他定义一次排列的跳跃为：
令 \(b_i\) 表示最大的 \({j}\ (i\le j\le n)\) 满足 \(a_j\ge a_i\) ，则 \(b_i=a_j\) 。最后对于所有 \(i=1\sim n\)，将 \(a_i\) 赋值为 \(b_i\)。
他想重复上述操作若干次。若操作 \({k}\) 次和操作 \({k+1}\) 次序列保持不变，那么跳跃停止，跳跃次数为 \({k}\)。他想知道排列会跳跃多少次，请你来帮他计算一下。
第一行， 输入一个数 \({n}\)。第二行输入 \({n}\) 个数，第 \(i\) 个数表示 \(a_i\)。
输出排列的跳跃次数。
经过 \(1\) 轮操作后，序列变成 \(\text{4 2 3 2}\)，经过 \(2\) 轮操作后，序列仍然是 \(\text{4 2 3 2}\)，因此排列跳跃了 \({1}\) 次。
经过 \(1\) 轮操作后，所有数都变成了 \(\text{10}\)，经过 \(2\) 轮操作后，序列仍然全都是 \(\text{10}\)，因此排列跳跃了 \({1}\) 次。
经过 \(1\) 轮操作后，序列仍然是 \(\text{8 7 6 5 4 3 2 1}\)，因此排列没有进行跳跃。
对于奇数编号的数据，满足给定的排列形如 \(n,n-1,\cdots,1\) 或 \(1,2,\cdots,n\)。对于 \(30\%\) 的数据，\(1\le n\le 1000\)；对于 \(70\%\) 的数据，\(1\le n\le 10^5\)；对于 \(100\%\) 的数据，\(1\le n\le 10^6\)。
找规律,模拟
假设我们已经经过了一次跳跃，\(a_i\rightarrow b_j\)\(\color{red}{是否还会有第二次跳跃？}\)不会。因为 \(j\) 取的是最靠右且大于 \(a_i\) 的值，第一次跳跃后，\(j\)后面的值还是不会大于 \(a_i\)所以，答案不会超过1，序列逆序时即0次跳跃
牛牛悄悄溜进了敌人的阵地，准备破坏敌人的城墙和防御法阵，破坏防御法阵可以给牛牛带来经验值。敌人的城墙分为 \(N\) 块，这些城墙排成一排，不成环。牛牛可以破坏 \(M\) 块城墙，他可以从任意一点开始不断破坏两侧相邻的城墙。每块城墙下方刻有诸多防御法阵。每个法阵需要耗费不同的时间来破坏。同时，为了防止对手发现，牛牛在每块城墙下仅能停留 \(T\) 秒。经过的时间忽略不计。破坏每个法阵会带来不同的经验值。并且，当相邻的城墙已经被破坏时，经验值会增加。举例来讲，假设牛牛在某块城墙收获 \(k\) 点经验值，但该城墙一侧（按照破坏顺序的规则，显然只有一侧可能被破坏）收获经验值为\(k_1\)，那么这块城墙的经验数变为\(k+k_1\)。而当某块城墙一侧有\(n\)块城墙被破坏，其实际收获的经验值为 \(k+k_1+k_2+...+k_n\)一段城墙得到的经验值为这一段城墙中每一段得到的经验值之和。显然，最终的经验值还和破坏顺序有关。现在，牛牛想知道他能得到的经验值最大是多少。
Note:上述的\(k_1,k_2,...,k_n\)是指城墙左侧（或右侧）连续nn个城墙被破坏时获得的经验值。
第一行三个整数 \(N,M,T\)，含义见题目描述。接下来 \(N\) 行，每行首先有正整数 \(K\) 表示该块城墙下方的法阵数量，接下来 \(2K\) 个正整数，依次是第 \(1\) 个法阵破坏后的经验值 \(v_i\) ，第 \(1\) 法阵破坏的用时 \(t_i\) 。第 \(2\) 个法阵破坏后的经验值和破坏用时，直到第 \(K\) 个法阵。
一个正整数，表示牛牛能够得到的最大经验值。
城墙共\(5\)段，每段在5秒内破坏，不计相邻城墙的破坏效果加成的情况下，依次能收到最多\(9,3,9,5,6\)点经验值。破坏\(3\)段，此时选择先破坏中间的城墙获得\(9\)点经验值，再依次获得\(5,6\)点经验值，最终能够造成最大\(52\)点经验值。计算过程如下\(9+(9+5)+[(9+9+5)+6]=529+(9+5)+[(9+9+5)+6]=52\)
对于 \(20\%\) 的数据，满足 \(K=1\)对于另外 \(20\%\) 的数据，满足 \(M=1\)对于额外\(20\%\) 的数据，满足 \(M\leq 3 ,K\leq 5\)对于 \(100\%\) 的数据，满足\(0<K\leq 50 ,0<T\leq 200 ,0<M<30, 0<N<10000\)\(0<v_i,t_i≤50\)保证答案在long long int范围内
01背包、区间dp
每个城墙可利用01背包求出最大经验，现在题目可转换为：给出 \(n\) 个数，从中有顺序地选出 \(m\) 个连续的数，使最终的结果最大