import java.io.*; import java.util.*; class Main { public static void main(String[] args) { new Main().run(); } class SegTree{ int n; int[] v; public SegTree(int n){ this.n=1; while(this.n0){ k=(k-1)/2; v[k]=Math.max(v[2*k+1],v[2*k+2]); } } int query(int a,int b){ return query(0,n,a,b,0); } int query(int l,int r,int a,int b,int k){ if(a<=l&&r<=b) return v[k]; else if(r<=a||b<=l) return 0; else{ int vl=query(l,(l+r)/2,a,b,2*k+1); int vr=query((l+r)/2,r,a,b,2*k+2); return Math.max(vl,vr); } } } 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]+seg[i-a[j][0]].query(0,j)); } if(j+1