def sac(E,P,i,temp):
    if temp[i][P]>0: return temp[i][P]
    if i == 0: return 0
    if E[i-1][0] > P:
        temp[i][P] = sac(E , P , i-1 ,temp)
        return temp[i][P]
    else:
        temp[i][P] = max( sac(E , P , i-1 , temp) , E[i-1][1] + sac(E , P - E[i-1][0] , i-1 , temp) )
        return temp[i][P]

def initSac(E,P):
    temp = [ [0] * (P+1) for i in range( len(E)+1 ) ]
    return sac(E , P , len(E) , temp)