문제
무한히 펼쳐진 x축의 직선형태의 거리에 여러개의 음료수 자판기들이 놓여 있다. 각 음료수 자판기들은 x축의 정수 좌표 위치에 놓여질 수 있으며, 동일한 위치에 여러개의 음료수 자판기가 놓여질 수 있다. 허나 여러개의 음료수 자판기가 동일한 위치에 놓여있을 경우 효율적이지 못하기 때문에 이를 적당히 새로이 배치 하고자 한다. 어떤 위치에 2개이상의 음료수 자판기가 있을 경우, 정확히 2개의 음료수 자판기를 선택하여 다음의 방법으로 이동시킬 수 있다.
해당 위치의 좌표를 x라고 할 경우, 한개의 음료수 자판기를 x-1 위치로 이동시키고, 다른 음료수 자판기 한 개를 x+1의 위치로 이동시켜야 한다. 이러한 이동방법을 통해서 각 좌표에는 1개 혹은 0개의 음료수 자판기가 놓여있게 하고자 한다. 예를 들어 다음과 같이 자판기가 놓여있다 하자.
... 0 0 2 1 2 0 0 ...
그러면 총 3번의 이동으로 자판기를 원하는대로 배치할 수 있다.
자판기를 원하는데로 배치를 하고자 할 때 최소의 이동횟수를 구하는 프로그램을 작성하라.
제출파일의 이름은 2275.cpp로하고 실행시간은 2초를 넘을 수 없다.
입력
첫번째 줄에는 자판기가 배치되어있는 좌표의 수 N(1<=N<=200)이 입력된다. 그 다음 줄 부터 N개의 줄에 자판기가 배치된 위치좌표와 배치된 자판기의 수가 입력된다.
배치된 자판기의 수의 합은 200 개가 넘지 않으며, 입력되는 위치 좌표의 범위는 -1,000,000 이상 1,000,000 이하의 정수다.
출력
문제에 설명된 조건을 만족하기 위한 최소의 이동횟수를 출력한다.
예제 #1
3
-1 2
0 1
1 2
3
예제 #2
2
-1000 1
2000 1
0
로그인해야 코드를 작성할 수 있어요.