Problem:


Problem D: Let's Go To School

Problem

がっちょ君は期末試験が近づくとやる気がなくなってしまい、しばしば学校を休むようになる。

期末試験まで残りN日である。

がっちょ君のi日目のやる気はXiであり、i日目に学校に行くために必要なやる気はYiである。

がっちょ君は Xi ≥ Yi となる日のみ学校に行く。

がっちょ君を心配したハジ君は、がっちょ君を励ますことで、可能な限り学校に行かせようと考えた。

ハジ君は最初、励まし力Pを持っている。

ハジ君がi日目に励まし力t(tは0以上の任意の実数)を消費してがっちょ君を励ますと、
がっちょ君のi日目のやる気はtだけ増加して、ハジ君の励まし力はtだけ減少する。さらに、i&plus;1 ≤ Nのとき、i&plus;1日目のがっちょ君のやる気Xi&plus;1はmax(0, Xi&plus;1 &minus; t) に変化する。

ハジ君は自分の持っている励まし力を超えて励ますことはできない。

ハジ君が最適な励まし方をしたときの、がっちょ君が学校に行く最大日数を求めよ。

Input

入力は以下の形式で与えられる。

N P
X1 Y1
X2 Y2
...
XN YN

  入力はすべて整数で与えられる。

  1行目に期末試験までの日数Nとハジ君が最初に持っている励まし力Pが空白区切りで与えられる。

  2行目から続くN行にはがっちょ君のi(i=1,2,...,N)日目のやる気Xiと学校に行くために必要なやる気Yiが空白区切りで与えられる。

Constraints

入力は以下の条件を満たす。

  
1 ≤ N ≤ 100

  
0 ≤ P ≤ 106

  
0 ≤ Xi ≤ 106

  
0 ≤ Yi ≤ 106

Output

  がっちょ君が学校に行くことができる最大の日数を1行に出力せよ。

Sample Input 1

3 10
1 6
5 10
0 5

Sample Output 1

2

Sample Input 2

5 5
1 1
1 2
1 2
1 3
1 3

Sample Output 2

4



Sample input:
3 10
1 6
5 10
0 5


Sample output:
2

Submission status: Wrong Answer

Solution code:
N,P=map(int,input().split())
xs=[]
ys=[]
dp=[[[1e9 for i in range(N+1)] for j in range(N+1)] for k in range(N+1)]
memo=[[0 for i in range(N+1)] for j in range(N+1)]
for i in range(N):
    x,y=map(int,input().split())
    xs.append(x)
    ys.append(y)

for start in range(N):
    for now in range(start,N+1):
        if(now==start):
            memo[start][now]=0
        else:
            nx=max(0,xs[now-1]-memo[start][now-1])
            memo[start][now]=memo[start][now-1]+max(0,ys[now-1]-nx)


dp[0][0][0]=0
for now in range(N):
    for l in range(now+1):
        for score in range(N):
           dp[now+1][l][score+1]=min(dp[now+1][l][score+1],dp[now][l][score]+memo[l][now+1]-memo[l][now])
           dp[now+1][now+1][score]=min(dp[now+1][now+1][score],dp[now][l][score])

ans=0
for l in range(N+1):
    for score in range(N):
        if(dp[N][l][score]<=P):
            ans=max(ans,score)


print(ans)

Submission status: Accepted

Solution code:
N,P=map(int,input().split())
xs=[]
ys=[]
dp=[[[1e9 for i in range(N+1)] for j in range(N+1)] for k in range(N+1)]
memo=[[0 for i in range(N+1)] for j in range(N+1)]
for i in range(N):
    x,y=map(int,input().split())
    xs.append(x)
    ys.append(y)

for start in range(N):
    preuse=0
    for now in range(start,N+1):
        if(now==start):
            preuse=0
            memo[start][now]=0
        else:
            nx=max(0,xs[now-1]-preuse)
            preuse=max(0,ys[now-1]-nx)
            memo[start][now]=memo[start][now-1]+preuse


dp[0][0][0]=0
for now in range(N):
    for l in range(now+1):
        for score in range(N):
           dp[now+1][l][score+1]=min(dp[now+1][l][score+1],dp[now][l][score]+memo[l][now+1]-memo[l][now])
           dp[now+1][now+1][score]=min(dp[now+1][now+1][score],dp[now][l][score])

ans=0
for l in range(N+1):
    for score in range(N):
        if(dp[N][l][score]<=P):
            ans=max(ans,score)


print(ans)