문제
Mr. JOI는 그의 수집실에 커다란 책상을 가지고 있으며, 책상 위에는 여러 개의 희귀한 동전이 놓여 있습니다. 책상을 정리하기 위해 그는 동전들을 재배치하려고 합니다.
이 책상은 가로 2,000,000,001 × 세로 2,000,000,001 크기의 격자로 간주할 수 있습니다. 왼쪽에서 오른쪽으로 열 번호는 −1,000,000,000부터 1,000,000,000까지이고, 아래에서 위로 행 번호는 −1,000,000,000부터 1,000,000,000까지입니다. 열 번호가 x이고 행 번호가 y인 셀은 (x, y)로 표시됩니다.
총 2N개의 동전이 있습니다. 현재 i번째 동전(1 ≤ i ≤ 2N)은 (Xi, Yi) 셀에 놓여 있습니다.
Mr. JOI의 목표는 모든 동전을 (x, y) (단, 1 ≤ x ≤ N 그리고 1 ≤ y ≤ 2) 위치에, 한 격자에 하나씩 배치하는 것입니다.
동전을 손상시키지 않기 위해 그가 수행할 수 있는 유일한 작업은 동전 하나를 선택하여 인접한 셀로 이동시키는 것입니다. (두 셀이 변을 공유할 때만 인접하다고 간주합니다.)
일시적으로 여러 개의 동전이 하나의 셀에 놓이는 것은 허용됩니다.
그는 목표를 달성하기 위해 최소한의 이동 횟수로 동전들을 배치하고자 합니다.
주어진 동전 개수와 현재 동전들의 위치가 주어졌을 때, 목표를 달성하기 위해 필요한 최소 이동 횟수를 계산하는 프로그램을 작성하세요.
입력
첫 줄에 N이 주어집니다. (
그 다음 2N개의 줄에 걸쳐 i번째 동전의 좌표가
출력
모든 동전을 (x, y) (단, 1 ≤ x ≤ N 그리고 1 ≤ y ≤ 2) 위치에, 한 격자에 하나씩 배치하는 최소 작업 횟수를 한 줄에 출력하세요.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 8점 | |
| #2 | 29점 | |
| #3 | 63점 | 추가 제한 없음 |
예제1
3
00
04
40
21
25
-11
15
예제2
4
21
21
21
31
31
31
31
31
9
예제3
5
10000000001000000000
-10000000001000000000
-1000000000-1000000000
1000000000-1000000000
-1-5
-22
28
47
-25
73
8000000029