시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 64 MB 559 213 158 38.725%

문제

수빈이는 좌표평면 위에 앉아있다. "나는 좌표평면이 너무 좋아!!" 라고 수빈이가 말했다. 좌표평면에는 N개의 사탕바구니가 있고, 각 사탕 바구니에는 M개의 사탕이 있다. 각 사탕 바구니는 (x1, y1), (x2, y2), …, (xn, yn)에 있고, 수빈이는 (0, 0)에 있다.

오늘은 날씨가 덥다. 따라서 시간이 1만큼 지날 때마다 모든 사탕바구니에서 사탕은 1만큼 줄어든다. 수빈이는 매우 배가 고프기 때문에, 사탕바구니에 있는 사탕을 순식간에 모두 먹을 수 있다. 수빈이가 1만큼 움직일 때, 시간은 1만큼 지나간다. 수빈이는 위쪽 (y-좌표가 늘어나는 방향) 또는 오른쪽 (x-좌표가 늘어나는 방향)으로만 움직일 수 있다.

수빈이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 주어진다.

둘째 줄부터 N개의 줄에 사탕 바구니의 위치 xi, yi가 주어진다. (0 ≤ N ≤ 300, 1 ≤ M ≤ 1,000,000, 0 ≤ xi, yi ≤ 300)

사탕 바구니의 위치는 중복되지 않는다.
 

출력

수빈이가 먹을 수 있는 사탕의 최대 개수를 출력한다.

예제 입력

3 15
1 1
3 1
1 6

예제 출력

24

힌트