package yukicoder; import java.util.Scanner; public class N561 { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int N=sc.nextInt(); int D=sc.nextInt(); int change=0; int[] T=new int[N]; int[] K=new int[N]; int cnt=0; int total=0; int max=0; for(int i=0;i<N;i++) { T[i]=sc.nextInt(); K[i]=sc.nextInt(); } for(int i=0;i<(int)Math.pow(2,N);i++) { total=0; change=0; for(int j=0;j<N;j++) { if((i&(int)Math.pow(2, j))!=0) { change++; total-=D; } total+=(change%2==0)?T[j]:K[j]; } max=(max<total)?total:max; } System.out.println(max); } }