쓰레기 수거

쓰레기장은 위치 0에 있고, 모든 수거 지점은 같은 직선 위에 있다. 쓰레기차는 쓰레기장에서 가까운 지점부터 차례로 방문하며, 각 지점의 쓰레기는 반드시 한 번에 모두 싣는다.

쓰레기차는 다음 상황 중 하나가 발생하면 현재 위치에서 쓰레기장으로 돌아가 싣고 있던 쓰레기를 비운다.

1. 쓰레기를 실은 뒤 적재량이 용량과 같아진 경우
2. 현재 지점의 쓰레기를 실으면 용량을 초과하는 경우
3. 더 방문할 수거 지점이 없는 경우

두 번째 경우에는 쓰레기차가 이미 현재 지점에 도착한 상태이다. 이때 쓰레기를 싣기 전에 쓰레기장에 다녀온 뒤, 같은 지점으로 돌아와 그 지점의 쓰레기를 싣는다. 한 지점의 쓰레기 중 일부만 싣고 나머지를 나중에 싣는 것은 허용되지 않는다.

쓰레기차의 용량과 각 지점의 거리 및 쓰레기 양이 주어질 때, 모든 쓰레기를 수거하고 쓰레기차가 쓰레기장으로 돌아올 때까지 이동한 총 거리를 구하라.

첫 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 줄에는 쓰레기차의 용량 W와 수거 지점의 개수 N이 주어진다. (1 <= W <= 1000, 1 <= N <= 1000)

다음 N개의 줄에는 i번째 지점의 쓰레기장으로부터의 거리 x_i와 그 지점의 쓰레기 양 w_i가 주어진다. 모든 x_i는 서로 다르며, 지점들은 x_i가 작은 순서대로 주어진다. (0 <= x_i <= 100000, 1 <= w_i <= W)

각 테스트 케이스마다 모든 쓰레기를 수거하고 쓰레기차가 쓰레기장으로 돌아올 때까지 이동한 총 거리를 출력한다.