wizardrabbit   3년 전

* 본 지문은 22153번 문제를 번역한 것입니다. 의역이 있을 수 있으며, 지문을 깔끔하게 작성할 목적으로 지문의 내용을 수정하거나 재작성했을 수도 있습니다.

문제

preview

게임 서버가 또 터지고야 말았다.

이 게임 서버의 대기열에는 현재 $N$ 명의 유저가 대기하고 있으며, $i$ 번째 유저는 대기열에 접속하는 시간 $r_i$ 초와 짜증 수치 $w_i$ 를 가지고 있다. 유저가 대기열에 접속한 후 매칭되기 위해 기다린 시간 $1$ 초 당 해당 유저의 짜증 수치만큼이 유저의 불만도에 더해진다. 예를 들어, 유저가 $2$ 초째에 대기열에 진입했고, 이 유저의 짜증 수치가 $3$ 이며, 매칭된 시간이 $6$ 초째일 경우 해당 유저가 가지게 되는 불만도는 $(6 - 2) \times 3 = 12$ 가 된다. 물론 유저가 대기열에 진입하자마자 매칭될 수도 있으며, 이 경우 해당 유저가 가지게 되는 불만도는 $0$ 이다.

불행히도 게임 서버는 느려 터졌기 때문에 $1$ 초에 $1$ 명의 유저밖에 매칭시킬 수 없다.

대기열에 접속하는 시간과 짜증 수치는 유저마다 제각각이기 때문에, 어떤 유저를 먼저 매칭시켜 주느냐에 따라 불만도는 달라질 수 있다. 게임 서버가 최적의 방법으로 모든 유저들을 매칭시켰다고 가정했을 때, 유저들이 느끼게 될 불만도의 합의 최솟값은 얼마나 될까?

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 첫 번째 줄에는 테스트 케이스의 개수 $T$ 가 주어진다. 그 다음 줄부터 테스트 케이스들이 차례로 주어진다.

각 테스트 케이스는 아래와 같이 주어진다.

N
r1 w1
r2 w2
r3 w3
...
rN-1 wN-1
rN wN

출력

각 테스트 케이스마다, 한 줄에 하나씩 유저들의 불만도의 합의 최솟값을 출력한다.

제한

● $r_i, w_i, N$ 은 자연수

● $1 \le r_i, w_i \le 10^6$

● 모든 테스트케이스에서의 $N$ 의 합은 $10^5$ 을 넘지 않는다.

댓글을 작성하려면 로그인해야 합니다.