// Arup Guha
// 3/9/2016
// Solution to 2015 MCPC Problem: Word Clouds Revisited

import java.util.*;

public class wordclouds {

	public static int n;
	public static int maxW;
	public static int[][] dim;

	public static int[] memo;

	public static void main(String[] args) {

		// Read in data.
		Scanner stdin = new Scanner(System.in);
		n = stdin.nextInt();
		maxW = stdin.nextInt();
		dim = new int[n][2];
		for (int i=0; i<n; i++)
			for (int j=0; j<2; j++)
				dim[i][j] = stdin.nextInt();

		// Store answers to recursive calls here.
		memo = new int[n];
		Arrays.fill(memo, -1);

		// Output result.
		System.out.println(solve(0));
	}

	// Returns the minimum height for clouds k..n-1.
	public static int solve(int k) {

		// Finished filling this in.
		if (k == n) return 0;

		// Figured this out already.
		if (memo[k] != -1) return memo[k];

		// Initital settings.
		int res = 1000000000;
		int curW = dim[k][0], curH = dim[k][1], index = k;

		// Go through until we can't fit on one row any more.
		while (curW <= maxW) {

			// Put in this row and solve recursively.
			int tmp = curH + solve(index+1);
			res = Math.min(res, tmp);
			index++;
			if (index == n) break;

			// Update current width and height of this row.
			curW += dim[index][0];
			curH = Math.max(curH, dim[index][1]);
		}

		// Store and return.
		return memo[k] = res;
	}
}