시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 64 MB 720 220 171 42.537%

문제

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

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

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

입력

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

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

사탕 바구니의 위치는 중복되지 않으며, (0, 0)에는 사탕이 없다.

출력

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

예제 입력 1

3 15
1 1
3 1
1 6

예제 출력 1

24

출처

University > 고려대학교 > 2017 고려대학교 프로그래밍 대회 F번