package yukicoder; import java.util.Scanner; public class Main { private static int[] tokyo; private static int[] kyoto; private static int days; private static int exp; private static int[][] dp; public static void main(String[] args) { // 自分の得意な言語で // Let's チャレンジ!! Scanner sc = new Scanner(System.in); days = sc.nextInt(); exp = sc.nextInt(); tokyo = new int[days]; kyoto = new int[days]; dp = new int[days][2]; for(int i = 0 ; i < days ; i++){ tokyo[i] = sc.nextInt(); kyoto[i] = sc.nextInt(); } int gain = greed(); System.out.println(gain); } private static int greed() { dp[0][0] = tokyo[0]; dp[0][1] = kyoto[0] - exp; for(int i = 0 ; i < days-1 ; i++){ dp[i+1][0] = max(dp[i][0] , dp[i][1] - exp) + tokyo[i+1]; dp[i+1][1] = max(dp[i][0] - exp , dp[i][1]) + kyoto[i+1]; } int tokyo = dp[days-1][0]; int kyoto = dp[days-1][1]; return tokyo > kyoto ? tokyo : kyoto; } private static int max(int i, int j) { return i > j ? i : j; } }