시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 64 MB | 1414 | 475 | 369 | 41.368% |
수빈이는 좌표평면 위에 앉아있다. "나는 좌표평면이 너무 좋아!!" 라고 수빈이가 말했다. 좌표평면에는 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)에는 사탕이 없다.
수빈이가 먹을 수 있는 사탕의 최대 개수를 출력한다.
3 15 1 1 3 1 1 6
24
University > 고려대학교 > 2017 고려대학교 프로그래밍 대회 > Div 1 B번
University > 고려대학교 > 2017 고려대학교 프로그래밍 대회 > Div 2 F번