체커
시간 제한2초메모리 제한128 MB
각 k에 대해 체커 k개 이상을 한 칸에 모으는 최소 이동 횟수를 구한다. 맨해튼 거리가 비용을 결정한다.
문제
아주 큰 보드 위에 체커 N개가 놓여 있다. i번째 체커는 (xi, yi)에 있다. 같은 칸에 여러 체커가 있어도 된다. 한 번의 이동은 체커 하나를 위, 왼쪽, 오른쪽, 아래 중 한 방향으로 한 칸 움직이는 것이다.
k = 1부터 N까지 각각에 대해, 적어도 k개의 체커가 같은 칸에 모이도록 만드는 데 필요한 이동 횟수의 최솟값을 구하라.
입력
첫째 줄에 N이 주어진다. N은 50 이하의 자연수이다.
둘째 줄부터 N개의 줄에는 각 체커의 x좌표와 y좌표가 주어진다. 모든 좌표는 1,000,000 이하의 자연수이다.
출력
첫째 줄에 정수 N개를 출력한다. k번째 정수는 적어도 k개의 체커가 같은 칸에 있도록 만들기 위해 필요한 이동 횟수의 최솟값이다.