핫도그 증식

여러 핫도그 노점상이 아주 긴 동서 방향 도로를 따라 있는 모퉁이(교차로)에서 핫도그를 팔기 시작했다. 문제는 여러 노점상이 같은 모퉁이에서 장사할 수도 있으며, 그러면 서로의 손님을 빼앗게 된다는 것이다. 하지만 아직 희망은 있다! 핫도그 노점상들에게는 계획이 있다.

같은 모퉁이에 둘 이상의 노점상이 있게 될 때마다, 그중 정확히 두 명이 다음을 의미하는 이동을 한 번 수행할 수 있다.

• 한 노점상은 도로를 따라 동쪽으로 한 모퉁이 더 이동한다.

• 다른 노점상은 도로를 따라 서쪽으로 한 모퉁이 더 이동한다. 도로는 매우 길기 때문에 모퉁이가 더 이상 없을 걱정은 하지 않아도 된다. 모든 핫도그 노점상의 시작 위치가 주어질 때, 모든 노점상이 서로 떨어질 때(즉, 모두 서로 다른 모퉁이에 있게 될 때)까지 수행해야 하는 최소 이동 횟수를 구해야 한다.

예를 들어, 도로의 각 모퉁이에 있는 핫도그 노점상의 수가 서쪽에서 동쪽 순서로 다음과 같다고 하자.

... 0 0 2 1 2 0 0 ...

그러면 아래와 같이 세 번의 이동으로 노점상들을 서로 떨어뜨릴 수 있다.

... 0 0 2 1 2 0 0 ...
        |
        +--- Do a move here

... 0 1 0 2 2 0 0 ...
          |
          +--- Do a move here

... 0 1 1 0 3 0 0 ...
            |
            +--- Do a move here

... 0 1 1 1 1 1 0 ...

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. 1 ≤ T ≤ 50. 1 ≤ C ≤ 200. 모든 P 값은 $[-1000000, 1000000]$ 범위에 있다. 각 테스트 케이스에서 모든 P 값은 서로 다르며 오름차순으로 나열된다. 모든 V 값은 양의 정수이다. 모든 V 값의 합에 대한 제한은 아래에 나와 있다. 유한한 횟수의 이동으로 핫도그 노점상들을 서로 떨어뜨리는 것이 항상 가능하다.

작은 데이터 세트 (테스트 세트 1 - 공개)

각 테스트 케이스의 전체 핫도그 노점상 수는 최대 200이다.

큰 데이터 세트 (테스트 세트 2 - 비공개)

각 테스트 케이스의 전체 핫도그 노점상 수는 최대 100000이다.

각 도로 모퉁이에는 양수 또는 음수인 정수가 붙어 있다. 각 i에 대해, 모퉁이 i+1는 모퉁이 i에서 동쪽으로 바로 다음 모퉁이를 가리킨다. 입력 파일에서는 이 번호 체계를 사용하여 모퉁이를 나타낸다.

입력 파일의 첫 번째 줄에는 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 케이스는 시작 배치에서 적어도 한 명의 핫도그 노점상이 있는 모퉁이의 수 C로 시작한다. 다음 C개의 줄에는 각각 공백으로 구분된 정수 한 쌍 P, V가 주어지며, 이는 모퉁이 P에 V명의 노점상이 있음을 나타낸다.

각 테스트 케이스마다 "Case #x: M"를 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 케이스 번호이고, M은 모든 노점상이 서로 다른 모퉁이에 있게 될 때까지 수행해야 하는 최소 이동 횟수이다.