시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 2445 1843 1692 77.014%

문제

해빈이는 학교를 다니면서 틈틈히 번 돈으로 자동차를 사려고 한다. 자동차에 여러가지 옵션을 포함시킬 수 있는데 해빈이는 덧셈과 곱셈을 하지 못하기 때문에 친구 태완이에게 도움을 청했다. 하지만 태완이도 덧셈과 곱셈을 못한다. 불쌍한 이 두 친구를 위해 모든 옵션이 주어진 자동차를 구매하는데 필요한 액수를 계산해 주자.

입력

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

각 테스트 케이스의 첫 줄엔 자동차의 가격 s가 주어진다. (1 ≤ s ≤ 100 000)

둘째 줄엔 해빈이가 구매하려고 하는 서로 다른 옵션의 개수 n이 주어진다. (0 ≤ n ≤ 1 000)

뒤이어 n개의 줄이 입력으로 들어온다. 각 줄은 q 와 p로 이루어져 있는데 q는 해빈이가 사려고 하는 특정 옵션의 개수이고 p는 해당 옵션의 가격이다. (1 ≤ q ≤ 100, 1 ≤ p ≤ 10 000)

출력

각 테스트 케이스 마다, 해빈이가 최종적으로 구매하려는 자동차의 가격을 한줄씩 출력한다.

예제 입력 1

2
10000
2
1 2000
3 400
50000
0

예제 출력 1

13200
50000
W3sicHJvYmxlbV9pZCI6IjkzMjUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1YmNcdWI5Yzg/IiwiZGVzY3JpcHRpb24iOiI8cD5cdWQ1NzRcdWJlNDhcdWM3NzRcdWIyOTQgXHVkNTU5XHVhZDUwXHViOTdjIFx1YjJlNFx1YjJjOFx1YmE3NFx1YzExYyBcdWQyYzhcdWQyYzhcdWQ3ODggXHViYzg4IFx1YjNjOFx1YzczY1x1Yjg1YyBcdWM3OTBcdWIzZDlcdWNjMjhcdWI5N2MgXHVjMGFjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNzkwXHViM2Q5XHVjYzI4XHVjNWQwIFx1YzVlY1x1YjdlY1x1YWMwMFx1YzljMCBcdWM2MzVcdWMxNThcdWM3NDQgXHVkM2VjXHVkNTY4XHVjMmRjXHVkMGFjIFx1YzIxOCBcdWM3ODhcdWIyOTRcdWIzNzAgXHVkNTc0XHViZTQ4XHVjNzc0XHViMjk0IFx1YjM2N1x1YzE0OFx1YWNmYyBcdWFjZjFcdWMxNDhcdWM3NDQgXHVkNTU4XHVjOWMwIFx1YmFiYlx1ZDU1OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVjZTVjXHVhZDZjIFx1ZDBkY1x1YzY0NFx1Yzc3NFx1YzVkMFx1YWM4YyBcdWIzYzRcdWM2YzBcdWM3NDQgXHVjY2FkXHVkNTg4XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MmbmJzcDtcdWQwZGNcdWM2NDRcdWM3NzRcdWIzYzQgXHViMzY3XHVjMTQ4XHVhY2ZjIFx1YWNmMVx1YzE0OFx1Yzc0NCBcdWJhYmJcdWQ1NWNcdWIyZTQuJm5ic3A7XHViZDg4XHVjMzBkXHVkNTVjIFx1Yzc3NCZuYnNwO1x1YjQ1MCBcdWNlNWNcdWFkNmNcdWI5N2MgXHVjNzA0XHVkNTc0IFx1YmFhOFx1YjRlMCBcdWM2MzVcdWMxNThcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0IFx1Yzc5MFx1YjNkOVx1Y2MyOFx1Yjk3YyBcdWFkNmNcdWI5ZTRcdWQ1NThcdWIyOTRcdWIzNzAgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YzU2MVx1YzIxOFx1Yjk3YyBcdWFjYzRcdWMwYjBcdWQ1NzQgXHVjOGZjXHVjNzkwLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4XHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiIFx1YzkwNFx1YzVkNCBcdWM3OTBcdWIzZDlcdWNjMjhcdWM3NTggXHVhYzAwXHVhY2E5IHNcdWFjMDAmbmJzcDtcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuJm5ic3A7KDEgJmxlOyBzICZsZTsgMTAwIDAwMCk8XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkNCBcdWQ1NzRcdWJlNDhcdWM3NzRcdWFjMDAgXHVhZDZjXHViOWU0XHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1OFx1YjI5NCZuYnNwO1x1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVjNjM1XHVjMTU4XHVjNzU4IFx1YWMxY1x1YzIxOCBuXHVjNzc0Jm5ic3A7XHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiZuYnNwOygwICZsZTsgbiAmbGU7IDEgMDAwKTxcL3A+XHJcblxyXG48cD5cdWI0YTRcdWM3NzRcdWM1YjQgblx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM3NzQgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YjRlNFx1YzViNFx1YzYyOFx1YjJlNC4gXHVhYzAxIFx1YzkwNFx1Yzc0MCZuYnNwO3EgXHVjNjQwIHBcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjI5NFx1YjM3MCZuYnNwO3FcdWIyOTQgXHVkNTc0XHViZTQ4XHVjNzc0XHVhYzAwIFx1YzBhY1x1YjgyNFx1YWNlMCBcdWQ1NThcdWIyOTQgXHVkMmI5XHVjODE1IFx1YzYzNVx1YzE1OFx1Yzc1OCBcdWFjMWNcdWMyMThcdWM3NzRcdWFjZTAgcFx1YjI5NCBcdWQ1NzRcdWIyZjkgXHVjNjM1XHVjMTU4XHVjNzU4IFx1YWMwMFx1YWNhOVx1Yzc3NFx1YjJlNC4gKDEgJmxlOyBxICZsZTsgMTAwLCAxICZsZTsgcCZuYnNwOyZsZTsgMTAgMDAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0IFx1YjljOFx1YjJlNCwgXHVkNTc0XHViZTQ4XHVjNzc0XHVhYzAwIFx1Y2Q1Y1x1Yzg4NVx1YzgwMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWI5ZTRcdWQ1NThcdWI4MjRcdWIyOTQgXHVjNzkwXHViM2Q5XHVjYzI4XHVjNzU4IFx1YWMwMFx1YWNhOVx1Yzc0NCBcdWQ1NWNcdWM5MDRcdWM1MjkgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjkzMjUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJIb3cgTXVjaD8iLCJkZXNjcmlwdGlvbiI6IjxwPlRoaXMgXHVmYjAxbmFuY2lhbCBjcmlzaXMhIEV2ZW4gTUk2JnJzcXVvO3MgdGVjaG5vbG9neSBkZXBhcnRtZW50IGRvZXMgbm90IGVzY2FwZSB0aGUgY29uc2VxdWVuY2VzLiBXaXRoIGFsbCB0aG9zZSBjb25zdHJhaW50cyBvbiB0aGUgYnVkZ2V0LCBob3cgY2FuIFIgYmUgZXhwZWN0ZWQgdG8gc3VwcGx5IG91ciBzcGllcyB3aXRoIGNhcnMgZXF1aXBwZWQgd2l0aCBhbGwgdGhlIHRlY2hub2xvZ2ljYWwgZ2FkZ2V0cyBhbmQgd2VhcG9ucnkgdGhleSBuZWVkIHRvIHNhdmUgdGhlIHdvcmxkPyBBcyBpZiBpdCBpcyBub3QgaGFyZCBlbm91Z2ggdG8gcHV0IGFsbCB0aG9zZSB0cmFja2luZyBzeXN0ZW1zLCBvaWwgc3ByYXllcnMsIGd1bnMsIGJ1bGxldHMgYW5kIG1pc3NpbGVzIGluIG9uZSBjYXIsIG5vdyBSIGhhcyB0byB3b3JyeSBhYm91dCB0aGUgY29zdHMgYXMgd2VsbC48XC9wPlxyXG5cclxuPHA+VGhlIG1hbmFnZW1lbnQgaW5zaXN0cywgdGhvdWdoOiBiZWZvcmUgUiBpcyBhbGxvd2VkIHRvIG9yZGVyIGEgY2FyIGFuZCBhbGwgdGhlIHBhcnRzIGhlIG5lZWRzLCBoZSB3aWxsIFx1ZmIwMXJzdCBuZWVkIHRvIGRldGVybWluZSB0aGUgZXhhY3QgYW1vdW50IG9mIG1vbmV5IHRoYXQgaGUgbmVlZHMuIE1hbmFnZW1lbnQgd2lsbCB0aGVuIGRlY2lkZSB3aGV0aGVyIGhlIGdldHMgdG8gcmVhbGl6ZSBoaXMgdmlzaW9uIG9yIG5vdC48XC9wPlxyXG5cclxuPHA+VGhpcyBzb3J0IG9mIGJ1cmVhdWNyYXRpYyBub25zZW5zZSBpcyBub3Qgc29tZXRoaW5nIHRoYXQgUiB3YW50cyB0byB3YXN0ZSBhbnkgdGltZSBvbi4gSGUgdGhlcmVmb3JlIHdhbnRzIHlvdSB0byBoZWxwIGhpbS4gR2l2ZW4gdGhlIHByaWNlIG9mIHRoZSBjYXIsIGEgbGlzdGluZyBvZiB0aGUgcGFydHMgUiB3YW50cyB0byBpbnN0YWxsLCBhbmQgdGhlIHByaWNlIHBlciBwaWVjZSBvZiBlYWNoIHBhcnQsIHdvcmsgb3V0IHdoYXQgdGhlIHRvdGFsIGNvc3QgaXMgb2YgdGhlIHByb2plY3QuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5PbiB0aGUgXHVmYjAxcnN0IGxpbmUgb25lIHBvc2l0aXZlIG51bWJlcjogdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLCBhdCBtb3N0IDEwMC4gQWZ0ZXIgdGhhdCBwZXIgdGVzdCBjYXNlOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPm9uZSBsaW5lIHdpdGggYW4gaW50ZWdlciBzICgxICZsZTsgcyAmbGU7IDEwMCAwMDApOiB0aGUgc3RvY2sgcHJpY2Ugb2YgdGhlIGNhci48XC9saT5cclxuXHQ8bGk+b25lIGxpbmUgd2l0aCBhbiBpbnRlZ2VyIG4gKDAgJmxlOyBuICZsZTsgMSAwMDApOiB0aGUgbnVtYmVyIG9mIGRpZmZlcmVudCBwYXJ0cyB0byBiZSBpbnN0YWxsZWQuPFwvbGk+XHJcblx0PGxpPm4gbGluZXMgd2l0aCB0d28gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzIHE8c3ViPmk8XC9zdWI+IGFuZCBwPHN1Yj5pPFwvc3ViPiAoMSAmbGU7IHE8c3ViPmk8XC9zdWI+ICZsZTsgMTAwIGFuZCAxICZsZTsgcDxzdWI+aTxcL3N1Yj4gJmxlOyAxMCAwMDApOiBmb3IgZWFjaCBkaWZmZXJlbnQgcGFydCBpLCB0aGUgbnVtYmVyIG9mIHBpZWNlcyBxPHN1Yj5pPFwvc3ViPiByZXF1aXJlZCBvZiBzdWNoIHBhcnQsIGFuZCB0aGUgcHJpY2UgcDxzdWI+aTxcL3N1Yj4gZm9yIGEgc2luZ2xlIHBpZWNlLjxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+UGVyIHRlc3QgY2FzZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5vbmUgbGluZSB3aXRoIGFuIGludGVnZXI6IHRoZSB0b3RhbCBhbW91bnQgb2YgbW9uZXkgbmVlZGVkIHRvIGJ1eSB0aGUgY2FyIGFuZCBhbGwgdGhlIHBhcnRzLjxcL2xpPlxyXG48XC91bD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d