题目内容

某市场举办小吃节，小吃节持续 n 天，每天都会有不同的小吃摊位入驻，每个摊位每天在投入一定的人力之后产生一定的营业额。

管理方希望在小吃节期间选择连续的若干天，使得这些天的总营业额最大。但是由于人力限制，选择这些天中总的人力不超过 K 人天。

请你计算出满足条件的最大营业额。

输入描述

第一行输入2个数字，分别是小吃节持续天数 n (0 < n < 100)，总的人力 K 人天 (0 < K < 10000)。

第二行到第 n+1 行，每一行输入2个数字，代表每天的营业额 (0 < j < 10000) 以及人力 m 人天 (0 < m < 1000, m < K)。

输出描述

在不超过 K 人天总人力限制的情况下，输出最大连续营业的营业额。

样例1

输入

6 6
3 1
1 2
5 3
2 2
7 2
4 4

输出

14

说明

小吃节持续6天，总人力限制6人天。

1. 第1天营业额为3，人力为1
2. 第2天营业额为1，人力为2
3. 第3天营业额为5，人力为1
4. 第4天营业额为2，人力为3
5. 第5天营业额为7，人力为2
6. 第6天营业额为4，人力为4

选择第3天到第5天，人力是1 + 3 + 2 = 6，不超过6人天，营业额总和为5 + 2 + 7 = 14，这是满足人力不超过6人天情况下的最大营业额。

样例2

输入

4 7
10 1
20 2
30 3
40 4

输出

70

说明

小吃节持续4天，总人力限制7人天。

1. 第1天营业额为10，人力为1
2. 第2天营业额为20，人力为2
3. 第3天营业额为30，人力为3
4. 第4天营业额为40，人力为4