레이팅 미적용무더운 여름날, 소 베시는 몹시 게으름을 피우고 싶다. 베시는 짧은 거리만 이동해도 최대한 많은 맛있는 풀에 닿을 수 있는 위치에 자리 잡으려고 한다.
베시의 들판에는 N개의 풀밭(1 <= N <= 100,000)이 있다. i번째 풀밭에는 g_i 단위의 풀(1 <= g_i <= 10,000)이 있고, 들판 위의 서로 다른 점 (x_i, y_i)(0 <= x_i, y_i <= 1,000,000)에 위치한다. 베시는 들판의 한 점(풀밭과 같은 점이어도 되고, 심지어 정수가 아닌 좌표의 점이어도 된다)을 초기 위치로 골라, 그 위치로부터 거리 K걸음(1 <= K <= 2,000,000) 이내에 있는 풀의 양이 최대가 되게 하려고 한다.
베시는 한 걸음을 내디딜 때 현재 위치에서 북, 남, 동, 서로 1 단위 이동한다. 예를 들어 (0,0)에서 (3,2)로 이동하려면 총 5걸음이 필요하다. 베시가 꼭 정수 크기의 걸음을 내디딜 필요는 없다.
베시가 가능한 최선의 초기 위치를 고른다면 닿을 수 있는 풀의 최대량을 구하는 것을 도와라.
첫째 줄: 정수 N과 K가 주어진다.
둘째 줄부터 1+N째 줄까지: i+1째 줄에는 i번째 풀밭을 나타내는 세 정수 g_i, x_i, y_i가 주어진다.
베시가 가능한 최선의 초기 위치에 자리 잡을 때 K걸음 이내에 닿을 수 있는 풀의 최대량을 출력한다.
lazy.in · 출력을 쓸 파일 lazy.out4 3
7 8 6
3 0 0
4 6 0
1 4 28Output details: By locating herself at (3,0), the grass at (0,0), (6,0), and (4,2) is all within K units of distance.