题解

题面描述

给定一个为期$n$天的小吃节，每天都有一个摊位，摊位第$i$天产生的营业额为$r_i$，消耗的人力为$m_i$。管理方希望选取一段连续的天数区间，使得这段区间内的总人力不超过$K$，且总营业额最大。求该最大总营业额。

思路

题目内容

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

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

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

输入描述

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

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

输出描述

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

样例1

输入

6 6
3 1
1 2
5 1
2 3
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$