import java.io.*; import java.util.*; class Main { public static void main(String[] args) { new Main().run(); } void run() { Scanner sc=new Scanner(System.in); int N=sc.nextInt(); int K=sc.nextInt(); int[] P=new int[N+1]; int[] D=new int[N+1]; int[][] a=new int[N+1][2]; for(int i=0;i(){ public int compare(int[] a,int[] b){ if(a[0]!=b[0]) return Integer.compare(a[0],b[0]); else return Integer.compare(a[1],b[1]); } }); ++N; int[][] dp=new int[K+1][N]; int[][] ma=new int[K+1][N]; for(int i=0;i<=K;++i){ for(int j=0;j0?dp[i-1][j]:0),(j>0?dp[i][j-1]:0)); ma[i][j]=Math.max((i>0?ma[i-1][j]:0),(j>0?ma[i][j-1]:0)); if(i-a[j][0]>=0){ dp[i][j]=Math.max(dp[i][j],a[j][1]+(j>0?seg[i-a[j][0]][j-1]:0)); } if(j+1