책장

농부 John이 $N$권($1 \le N \le 100000$)의 책을 모았고, 이 책들을 모두 꽂을 책장을 만들려고 합니다.

각 책 $i$에는 너비 $W(i)$와 높이 $H(i)$가 있습니다. 책은 반드시 순서대로 선반에 꽂아야 합니다. 즉, 첫 번째 선반에는 어떤 $k$에 대해 책 $1 \dots k$가 꽂히고, 두 번째 선반은 책 $k+1$부터 시작하며, 이런 식으로 이어집니다. 한 선반에 꽂힌 책들의 너비 합은 최대 $L$($1 \le L \le 10^9$)까지 가능합니다.

한 선반의 높이는 그 선반에 꽂힌 책 중 가장 높은 책의 높이와 같고, 책장 전체의 높이는 모든 선반의 높이를 더한 값입니다(선반들은 세로로 쌓여 있습니다).

책장 전체의 높이가 될 수 있는 최솟값을 구하세요.

첫째 줄에 두 정수 $N$과 $L$이 공백으로 구분되어 주어집니다.

다음 $N$개의 줄 중 $i$번째 줄에는 책 $i$의 높이 $H(i)$와 너비 $W(i)$가 공백으로 구분되어 주어집니다($1 \le H(i) \le 10^6$, $1 \le W(i) \le L$).

책장 전체의 높이가 될 수 있는 최솟값을 한 줄에 출력하세요.

첫 번째 예제에서는 책이 $5$권 있고, 각 선반의 너비 합은 최대 $10$까지 가능합니다. 최적의 배치 중 하나는 선반 $3$개를 사용합니다. 첫 번째 선반에는 책 $1$(높이 $5$, 너비 $7$)만, 두 번째 선반에는 책 $2 \dots 4$(높이 $9, 8, 13$이므로 선반 높이는 $13$, 너비 합은 $9$), 세 번째 선반에는 책 $5$(높이 $3$, 너비 $8$)를 꽂습니다. 전체 높이는 $5 + 13 + 3 = 21$입니다.