美丽的项链

动态规划+背包问题
参考：https://blog.csdn.net/sinat_32403451/article/details/84899820
背包问题及变形：https://blog.csdn.net/qq_22526061/article/details/83504116

#coding:utf-8
n,m = map(int,input().split())
L=[]
R=[]
for i in range(n):
    li,ri = map(int,input().split())
    L.append(li)
    R.append(ri)

dp = [[0 for i in range(m+1)] for j in range(n)]

#初始化第一行
for i in range(L[0],R[0]+1):
    dp[0][i] = 1

#剩余其他行使用公式进行计算
for i in range(1,n):
    for j in range(m+1):
        left = max(0,j-R[i])
        right = max(0,j-L[i])
        for l in range(left,right+1):
            dp[i][j] += dp[i-1][l]
#print(dp)
print(dp[n-1][m])