시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 9 7 7 87.500%

문제

쓰레기장에서 출발한 쓰레기차가 여러 지점들을 방문하며 쓰레기를 모으고 있다. 쓰레기차는 쓰레기장에서 가까운 지점부터 방문하며, 쓰레기를 모으다가 다음과 같은 경우에 쓰레기장으로 돌아가 싣고 있는 쓰레기를 비운다.

  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)

출력

각 테스트 케이스에 대하여, 쓰레기차가 모든 쓰레기를 수거하여 쓰레기장에 도달할 때까지 움직인 거리를 출력한다.

예제 입력 1

3
2 2
1 1
2 2
6 3
1 1
2 2
3 3
3 3
1 2
2 2
3 1

예제 출력 1

8
6
10
W3sicHJvYmxlbV9pZCI6IjE2ODAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM0ZjBcdWI4MDhcdWFlMzAgXHVjMjE4XHVhYzcwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM0ZjBcdWI4MDhcdWFlMzBcdWM3YTVcdWM1ZDBcdWMxMWMgXHVjZDljXHViYzFjXHVkNTVjIFx1YzRmMFx1YjgwOFx1YWUzMFx1Y2MyOFx1YWMwMCBcdWM1ZWNcdWI3ZWMgXHVjOWMwXHVjODEwXHViNGU0XHVjNzQ0IFx1YmMyOVx1YmIzOFx1ZDU1OFx1YmE3MCBcdWM0ZjBcdWI4MDhcdWFlMzBcdWI5N2MgXHViYWE4XHVjNzNjXHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVjNGYwXHViODA4XHVhZTMwXHVjYzI4XHViMjk0IFx1YzRmMFx1YjgwOFx1YWUzMFx1YzdhNVx1YzVkMFx1YzExYyBcdWFjMDBcdWFlNGNcdWM2YjQgXHVjOWMwXHVjODEwXHViZDgwXHVkMTMwIFx1YmMyOVx1YmIzOFx1ZDU1OFx1YmE3MCwgXHVjNGYwXHViODA4XHVhZTMwXHViOTdjIFx1YmFhOFx1YzczY1x1YjJlNFx1YWMwMCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YWNiZFx1YzZiMFx1YzVkMCBcdWM0ZjBcdWI4MDhcdWFlMzBcdWM3YTVcdWM3M2NcdWI4NWMgXHViM2NjXHVjNTQ0XHVhYzAwIFx1YzJlM1x1YWNlMCBcdWM3ODhcdWIyOTQgXHVjNGYwXHViODA4XHVhZTMwXHViOTdjIFx1YmU0NFx1YzZiNFx1YjJlNC48XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5cdWM0ZjBcdWI4MDhcdWFlMzBcdWM3NTggXHVjNTkxXHVjNzc0IFx1YzZhOVx1YjdjOVx1YzVkMCBcdWIzYzRcdWIyZWNcdWQ1ODhcdWM3NDQgXHViNTRjLjxcL2xpPlxyXG5cdDxsaT5cdWFkZjggXHVjOWMwXHVjODEwXHVjNzU4IFx1YzRmMFx1YjgwOFx1YWUzMFx1Yjk3YyBcdWMyZTRcdWM1YzhcdWM3NDQgXHViNTRjIFx1YzRmMFx1YjgwOFx1YWUzMFx1Y2MyOFx1Yzc1OCBcdWM2YTlcdWI3YzlcdWM3NDQgXHViMTE4XHVhYzhjIFx1YjQyMCBcdWI1NGMuPFwvbGk+XHJcblx0PGxpPlx1YjM1NCBcdWM3NzRcdWMwYzEgXHVjNGYwXHViODA4XHVhZTMwXHViOTdjIFx1YzJlNFx1Yzc0NCBcdWM5YzBcdWM4MTBcdWM3NzQgXHVjNWM2XHVjNzQ0IFx1YjU0Yy48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5cdWM0ZjBcdWI4MDhcdWFlMzAgXHViYWE4XHVjNzNjXHVhZTMwXHViMjk0IFx1YzRmMFx1YjgwOFx1YWUzMFx1Y2MyOFx1YWMwMCBcdWJhYThcdWI0ZTAgXHVjOWMwXHVjODEwXHVjNzU4IFx1YzRmMFx1YjgwOFx1YWUzMFx1Yjk3YyBcdWMyMThcdWFjNzBcdWQ1NThcdWM1ZWMgXHVjNGYwXHViODA4XHVhZTMwXHVjN2E1XHVjNWQwIFx1YjNjNFx1YjJlY1x1ZDU4OFx1Yzc0NCBcdWI1NGMgXHViMDVkXHViMDljXHViMmU0LiBcdWI2MTBcdWQ1NWMsIFx1YzRmMFx1YjgwOFx1YWUzMFx1Y2MyOFx1YWMwMCBcdWQyYjlcdWM4MTUgXHVjOWMwXHVjODEwXHVjNWQwXHVjMTFjIFx1YzRmMFx1YjgwOFx1YWUzMFx1Yjk3YyBcdWMyZTRcdWM3NDQgXHViNTRjXHViMjk0IFx1ZDU1YyBcdWJjODhcdWM1ZDAgXHViYWE4XHViNDUwIFx1YzJlNFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuKFx1Yzk4OSwgXHVjNGYwXHViODA4XHVhZTMwXHVjNzU4IFx1Yzc3Y1x1YmQ4MFx1Yjk3YyBcdWMyZTNcdWFjZTAgXHVjNGYwXHViODA4XHVhZTMwXHVjN2E1XHVjNWQwIFx1YjJlNFx1YjE0MFx1YzYyOCBcdWI0YTQgXHViMDk4XHViYTM4XHVjOWMwXHViOTdjIFx1YzJlM1x1YjI5NCBcdWFjODNcdWM3NDAgXHVkNWM4XHVjNmE5XHViNDE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4pPFwvcD5cclxuXHJcbjxwPlx1YzRmMFx1YjgwOFx1YWUzMFx1Y2MyOFx1Yzc1OCBcdWM2YTlcdWI3YzlcdWFjZmMgXHVhYzAxIFx1YzljMFx1YzgxMFx1Yzc1OCBcdWM3MDRcdWNlNThcdWM2NDAgXHVjNGYwXHViODA4XHVhZTMwXHVjNzU4IFx1YzU5MVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM3MDRcdWM3NTggXHViYzI5XHViYzk1XHVjYzk4XHViN2ZjIFx1YzRmMFx1YjgwOFx1YWUzMFx1Y2MyOFx1YWMwMCBcdWJhYThcdWI0ZTAgXHVjNGYwXHViODA4XHVhZTMwXHViNGU0XHVjNzQ0IFx1YzRmMFx1YjgwOFx1YWUzMFx1YzdhNVx1YzVkMCBcdWMyMThcdWFjNzBcdWQ1ODhcdWM3NDQgXHViNTRjIFx1YzRmMFx1YjgwOFx1YWUzMFx1Y2MyOFx1Yzc1OCBcdWNkMWQgXHVjNzc0XHViM2Q5IFx1YWM3MFx1YjlhY1x1Yjk3YyBcdWFkNmNcdWQ1NThcdWM3OTAuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NTggXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWMyMTggVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzRmMFx1YjgwOFx1YWUzMFx1Y2MyOFx1Yzc1OCBcdWM2YTlcdWI3YzkgV1x1YzY0MCBcdWM5YzBcdWM4MTBcdWM3NTggXHVhYzJmXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiZuYnNwOzxzcGFuIHN0eWxlPVwibGluZS1oZWlnaHQ6MS42ZW1cIj4oMSAmbHQ7PSBXICZsdDs9IDEwMDAsIDEgJmx0Oz0gTiAmbHQ7PSAxMDAwKTxcL3NwYW4+PFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBpXHViYzg4XHVjOWY4IFx1YzljMFx1YzgxMFx1Yzc1OCBcdWM0ZjBcdWI4MDhcdWFlMzBcdWM3YTVcdWM3M2NcdWI4NWNcdWJkODBcdWQxMzBcdWM3NTggXHVhYzcwXHViOWFjIHhfaVx1YzY0MCBcdWM0ZjBcdWI4MDhcdWFlMzBcdWM3NTggXHVjNTkxIHdfaVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWM5YzBcdWM4MTBcdWM3NTggeF9pXHViMjk0IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzRcdWJhNzAgeF9pXHVhYzAwIFx1Yzc5MVx1Yzc0MCBcdWM5YzBcdWM4MTBcdWJkODBcdWQxMzAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1Yzc4NVx1YjgyNVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuJm5ic3A7PHNwYW4gc3R5bGU9XCJsaW5lLWhlaWdodDoxLjZlbVwiPigwICZsdDs9IHhfaSAmbHQ7PSAxMDAwMDAsIDEgJmx0Oz0gd19pICZsdDs9IFcpPFwvc3Bhbj48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NThcdWM1ZWMsIFx1YzRmMFx1YjgwOFx1YWUzMFx1Y2MyOFx1YWMwMCBcdWJhYThcdWI0ZTAgXHVjNGYwXHViODA4XHVhZTMwXHViOTdjIFx1YzIxOFx1YWM3MFx1ZDU1OFx1YzVlYyBcdWM0ZjBcdWI4MDhcdWFlMzBcdWM3YTVcdWM1ZDAgXHViM2M0XHViMmVjXHVkNTYwIFx1YjU0Y1x1YWU0Y1x1YzljMCBcdWM2YzBcdWM5YzFcdWM3NzggXHVhYzcwXHViOWFjXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxNjgwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiR2FyYmFnZSBDb2xsZWN0aW9uIiwiZGVzY3JpcHRpb24iOiI8cD5HYXJiYWdlIHRydWNrIGlzIGNvbGxlY3RpbmcgZ2FyYmFnZSBvbiBpdHMgcm91dGUgc3RhcnRpbmcgYXQgdGhlIGR1bXAgYW5kIGNvbGxlY3RpbmcgZ2FyYmFnZSBmcm9tIHBpY2sgdXAgcG9pbnRzIGluIG9yZGVyIChjbG9zZXN0IGZpcnN0KS4gR2FyYmFnZSB0cnVjayByZXR1cm5zIHRvIHRoZSBkdW1wIGFuZCBlbXB0aWVzIGl0cyBjb250ZW50cyBpZiBpdCBlaXRoZXI8XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5pcyBmdWxsIG9yPFwvbGk+XHJcblx0PGxpPmNhbm5ub3QgbG9hZCB0aGUgZ2FyYmFnZSBhdCB0aGUgY3VycmVudCBwb2ludCBiZWNhdXNlIGl0IHdpbGwgcHV0IHRoZSBsb2FkIG92ZXIgdGhlIHdlaWdodCBsaW1pdCAodGhlIHRydWNrIGRyaXZlciBoYXMgbm8gd2F5IG9mIGtub3dpbmcgdGhlIHdlaWdodCBvZiB0aGUgZ2FyYmFnZSBhdCBhIHBhcnRpY3VsYXIgcGljayB1cCBwb2ludCB1bnRpbCB0aGUgdHJ1Y2sgcmVhY2hlcyB0aGF0IHBvaW50KSBvcjxcL2xpPlxyXG5cdDxsaT50aGVyZSBhcmUgbm8gbW9yZSBwaWNrIHVwIHBvaW50cyBsZWZ0PFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+VGhlIHBpY2sgdXAgcnVuIGVuZHMgd2hlbiB0aGUgdHJ1Y2sgcmV0dXJucyB0byB0aGUgZHVtcCBhZnRlciB0aGUgY2FzZSAjMy4gSW4gdGhlIGNhc2Ugd2hlcmUgYm90aCBydWxlICMxIGFuZCBydWxlICMzIGFwcGx5LCB3ZSBjb25zaWRlciBvbmx5IHRoZSBsYXR0ZXIgb25lICh0aGUgcnVuIGlzIG92ZXIpLiBBbHNvIG5vdGUgdGhhdCB0aGVyZSBhcmUgbm8gcGFydGlhbCBwaWNrIHVwcyAoZS5nLiB0aGlzIGlzIG5vdCBhbGxvd2VkOiBnZXQgYSBwb3J0aW9uIG9mIGdhcmJhZ2UgYXQgc29tZSBwb2ludCB1bnRpbCB0cnVjayBpcyBmdWxsIGFuZCBjb21lIGJhY2sgZm9yIHRoZSByZXN0KS48XC9wPlxyXG5cclxuPHA+R2l2ZW4gdGhlIHdlaWdodCBsaW1pdCB0aGF0IHRydWNrIGNhbiBjYXJyeSBhbmQgdGhlIGxpc3Qgb2YgcGljayB1cCBwb2ludHMgd2l0aCBnYXJiYWdlIHdlaWdodHMsIHdoYXQgaXMgdGhlIGRpc3RhbmNlIHRoYXQgdGhlIHRydWNrIHdpbGwgY292ZXIgZm9sbG93aW5nIHRoZSBydWxlcyBhYm92ZT88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPklucHV0IHN0YXJ0cyB3aXRoIGFuIGludGVnZXIgVCBvbiB0aGUgZmlyc3QgbGluZSwgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLiBFYWNoIGNhc2Ugc3RhcnRzIHdpdGggdGhlIGxpbmUgd2l0aCB0d28gaW50ZWdlcnMgVyBhbmQgTiwgdGhlIHdlaWdodCBsaW1pdCBhbmQgdGhlIG51bWJlciBvZiBwaWNrIHVwIHBvaW50cywgcmVzcGVjdGl2ZWx5LjxcL3A+XHJcblxyXG48cD5UaGVuIE4gbGluZXMgZm9sbG93LCBlYWNoIGNvbnRhaW5pbmcgaW50ZWdlcnMgeF9pIGFuZCB3X2ksIHRoZSBkaXN0YW5jZSBmcm9tIHRoZSBkdW1wIGFuZCB0aGUgd2VpZ2h0IG9mIHRoZSBnYXJiYWdlIGF0IHRoZSBwaWNrIHVwIHBvaW50IHJlc3BlY3RpdmVseS48XC9wPlxyXG5cclxuPHA+Q29uc3RyYWludHMgYXJlIGFzIGdpdmVuOiAxJmx0Oz1XJmx0Oz0xMDAwLCAxJmx0Oz1OJmx0Oz0xMDAwLCAwJmx0O3hfaSZsdDs9MTAwLDAwMCwgMSZsdDs9d19pJmx0Oz1XLiBEaXN0YW5jZXMgYXJlIGRpc3RpbmN0IGFuZCBnaXZlbiBpbiBvcmRlciwgaS5lLiBmb3IgZWFjaCBpJmx0O2osIHhfaSZsdDt4X2ouPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlIG91dHB1dCBhbiBpbnRlZ2VyIG9uIGEgbGluZSAtIHRoZSBkaXN0YW5jZSBjb3ZlcmVkIGJ5IHRoZSBnYXJiYWdlIHRydWNrLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==