전자 대기열 시스템

최근 몇 년 사이 전자 대기열은 일상에 깊숙이 자리 잡았다. 많은 관공서에서 번호표를 뽑는 단말기를 볼 수 있고, 방문객들은 "마지막 분이 누구세요?"라는 질문을 하지 않고도 전자 게시판을 통해 얼마나 더 기다려야 하는지, 자신의 차례가 언제 오는지 알 수 있다.

그러나 이런 시스템은 아직 완벽과 거리가 멀다. 예를 들어 모든 대기열의 기본 원칙인 "먼저 온 사람이 먼저 서비스를 받는다"는 의문을 제기한다. 혁신적인 전자 대기열 시스템을 개발할 때 이 원칙을 반드시 지킬 필요가 없도록 만들기로 했다. 대신 새 시스템은 줄을 서 있는 사람들을 접수하는 공무원에게 돌아가는 부정적인 감정의 양을 최소화하는 것을 목표로 한다.

각 사람에게는 짜증 지수라는 기준이 있다고 알려져 있다. 이 매개변수가 w이면, 대기열에서 t시간을 기다린 후 이 사람은 공무원에게 정확히 wt단위의 분노와 욕설을 퍼붓는다. 예를 들어 방문객이 도착한 직후 서비스를 받기 시작하면 공무원은 피해를 입지 않지만, 방문객이 3시 초에 도착했는데 서비스가 5시 초에야 시작되면 분노의 양은 2w가 된다.

또한 각 방문객을 서비스하는 데는 정확히 1시간이 걸리고, 각 방문객은 특정 시간의 시작에 도착한다. 주어진 짜증 지수와 방문객의 도착 시간을 바탕으로, 최적의 서비스 순서로 방문객을 처리할 때 공무원이 받게 될 부정적인 감정의 총량을 구하는 것이 과제이다.

첫 번째 줄에는 처리해야 할 사례의 수를 나타내는 정수 t가 주어진다. 그다음 t개의 사례 설명이 이어진다.

각 사례 설명은 첫 번째 줄의 방문객 수 n과 n명의 방문객 설명으로 구성된다. 각 방문객에 대해 별도의 줄에 두 정수 ri와 wi (1 ≤ ri, wi ≤ 106)가 주어진다. 이는 각각 방문객이 도착한 시간의 번호와 짜증 지수이다.

한 테스트의 모든 사례에서 방문객의 총 수는 105를 초과하지 않는다.

각 사례에 대해 별도의 줄에 공무원이 받게 될 최소 총 부정적인 감정의 양을 출력한다.