시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 2510 1900 1749 77.253%

문제

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

입력

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

각 테스트 케이스의 첫 줄엔 자동차의 가격 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/IiwiZGVzY3JpcHRpb24iOiI8cD5cdWQ1NzRcdWJlNDhcdWM3NzRcdWIyOTQgXHVkNTU5XHVhZDUwXHViOTdjIFx1YjJlNFx1YjJjOFx1YmE3NFx1YzExYyBcdWQyYzhcdWQyYzhcdWQ3ODggXHViYzg4IFx1YjNjOFx1YzczY1x1Yjg1YyBcdWM3OTBcdWIzZDlcdWNjMjhcdWI5N2MgXHVjMGFjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNzkwXHViM2Q5XHVjYzI4XHVjNWQwIFx1YzVlY1x1YjdlYyBcdWFjMDBcdWM5YzAgXHVjNjM1XHVjMTU4XHVjNzQ0IFx1ZDNlY1x1ZDU2OFx1YzJkY1x1ZDBhYyBcdWMyMTggXHVjNzg4XHViMjk0XHViMzcwIFx1ZDU3NFx1YmU0OFx1Yzc3NFx1YjI5NCBcdWIzNjdcdWMxNDhcdWFjZmMgXHVhY2YxXHVjMTQ4XHVjNzQ0IFx1ZDU1OFx1YzljMCBcdWJhYmJcdWQ1NThcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1Y2U1Y1x1YWQ2YyBcdWQwZGNcdWM2NDRcdWM3NzRcdWM1ZDBcdWFjOGMgXHViM2M0XHVjNmMwXHVjNzQ0IFx1Y2NhZFx1ZDU4OFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjJm5ic3A7XHVkMGRjXHVjNjQ0XHVjNzc0XHViM2M0IFx1YjM2N1x1YzE0OFx1YWNmYyBcdWFjZjFcdWMxNDhcdWM3NDQgXHViYWJiXHVkNTVjXHViMmU0LiZuYnNwO1x1YmQ4OFx1YzMwZFx1ZDU1YyBcdWM3NzQmbmJzcDtcdWI0NTAgXHVjZTVjXHVhZDZjXHViOTdjIFx1YzcwNFx1ZDU3NCBcdWJhYThcdWI0ZTAgXHVjNjM1XHVjMTU4XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNCBcdWM3OTBcdWIzZDlcdWNjMjhcdWI5N2MgXHVhZDZjXHViOWU0XHVkNTU4XHViMjk0XHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWM1NjFcdWMyMThcdWI5N2MgXHVhY2M0XHVjMGIwXHVkNTc0IFx1YzhmY1x1Yzc5MC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWIgXHVjOTA0XHVjNWQ0IFx1Yzc5MFx1YjNkOVx1Y2MyOFx1Yzc1OCBcdWFjMDBcdWFjYTkgc1x1YWMwMCZuYnNwO1x1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4mbmJzcDsoMSAmbGU7IHMgJmxlOyAxMDAgMDAwKTxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQ0IFx1ZDU3NFx1YmU0OFx1Yzc3NFx1YWMwMCBcdWFkNmNcdWI5ZTRcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTU4XHViMjk0Jm5ic3A7XHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWM2MzVcdWMxNThcdWM3NTggXHVhYzFjXHVjMjE4IG5cdWM3NzQmbmJzcDtcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuJm5ic3A7KDAgJmxlOyBuICZsZTsgMSAwMDApPFwvcD5cclxuXHJcbjxwPlx1YjRhNFx1Yzc3NFx1YzViNCBuXHVhYzFjXHVjNzU4IFx1YzkwNFx1Yzc3NCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHViNGU0XHVjNWI0XHVjNjI4XHViMmU0LiBcdWFjMDEgXHVjOTA0XHVjNzQwJm5ic3A7cSBcdWM2NDAgcFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMjk0XHViMzcwJm5ic3A7cVx1YjI5NCBcdWQ1NzRcdWJlNDhcdWM3NzRcdWFjMDAgXHVjMGFjXHViODI0XHVhY2UwIFx1ZDU1OFx1YjI5NCBcdWQyYjlcdWM4MTUgXHVjNjM1XHVjMTU4XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yzc3NFx1YWNlMCBwXHViMjk0IFx1ZDU3NFx1YjJmOSBcdWM2MzVcdWMxNThcdWM3NTggXHVhYzAwXHVhY2E5XHVjNzc0XHViMmU0LiAoMSAmbGU7IHEgJmxlOyAxMDAsIDEgJmxlOyBwJm5ic3A7JmxlOyAxMCAwMDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTQgXHViOWM4XHViMmU0LCBcdWQ1NzRcdWJlNDhcdWM3NzRcdWFjMDAgXHVjZDVjXHVjODg1XHVjODAxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YjllNFx1ZDU1OFx1YjgyNFx1YjI5NCBcdWM3OTBcdWIzZDlcdWNjMjhcdWM3NTggXHVhYzAwXHVhY2E5XHVjNzQ0IFx1ZDU1Y1x1YzkwNFx1YzUyOSBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiOTMyNSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkhvdyBNdWNoPyIsImRlc2NyaXB0aW9uIjoiPHA+VGhpcyBcdWZiMDFuYW5jaWFsIGNyaXNpcyEgRXZlbiBNSTYmcnNxdW87cyB0ZWNobm9sb2d5IGRlcGFydG1lbnQgZG9lcyBub3QgZXNjYXBlIHRoZSBjb25zZXF1ZW5jZXMuIFdpdGggYWxsIHRob3NlIGNvbnN0cmFpbnRzIG9uIHRoZSBidWRnZXQsIGhvdyBjYW4gUiBiZSBleHBlY3RlZCB0byBzdXBwbHkgb3VyIHNwaWVzIHdpdGggY2FycyBlcXVpcHBlZCB3aXRoIGFsbCB0aGUgdGVjaG5vbG9naWNhbCBnYWRnZXRzIGFuZCB3ZWFwb25yeSB0aGV5IG5lZWQgdG8gc2F2ZSB0aGUgd29ybGQ/IEFzIGlmIGl0IGlzIG5vdCBoYXJkIGVub3VnaCB0byBwdXQgYWxsIHRob3NlIHRyYWNraW5nIHN5c3RlbXMsIG9pbCBzcHJheWVycywgZ3VucywgYnVsbGV0cyBhbmQgbWlzc2lsZXMgaW4gb25lIGNhciwgbm93IFIgaGFzIHRvIHdvcnJ5IGFib3V0IHRoZSBjb3N0cyBhcyB3ZWxsLjxcL3A+XHJcblxyXG48cD5UaGUgbWFuYWdlbWVudCBpbnNpc3RzLCB0aG91Z2g6IGJlZm9yZSBSIGlzIGFsbG93ZWQgdG8gb3JkZXIgYSBjYXIgYW5kIGFsbCB0aGUgcGFydHMgaGUgbmVlZHMsIGhlIHdpbGwgXHVmYjAxcnN0IG5lZWQgdG8gZGV0ZXJtaW5lIHRoZSBleGFjdCBhbW91bnQgb2YgbW9uZXkgdGhhdCBoZSBuZWVkcy4gTWFuYWdlbWVudCB3aWxsIHRoZW4gZGVjaWRlIHdoZXRoZXIgaGUgZ2V0cyB0byByZWFsaXplIGhpcyB2aXNpb24gb3Igbm90LjxcL3A+XHJcblxyXG48cD5UaGlzIHNvcnQgb2YgYnVyZWF1Y3JhdGljIG5vbnNlbnNlIGlzIG5vdCBzb21ldGhpbmcgdGhhdCBSIHdhbnRzIHRvIHdhc3RlIGFueSB0aW1lIG9uLiBIZSB0aGVyZWZvcmUgd2FudHMgeW91IHRvIGhlbHAgaGltLiBHaXZlbiB0aGUgcHJpY2Ugb2YgdGhlIGNhciwgYSBsaXN0aW5nIG9mIHRoZSBwYXJ0cyBSIHdhbnRzIHRvIGluc3RhbGwsIGFuZCB0aGUgcHJpY2UgcGVyIHBpZWNlIG9mIGVhY2ggcGFydCwgd29yayBvdXQgd2hhdCB0aGUgdG90YWwgY29zdCBpcyBvZiB0aGUgcHJvamVjdC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPk9uIHRoZSBcdWZiMDFyc3QgbGluZSBvbmUgcG9zaXRpdmUgbnVtYmVyOiB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMsIGF0IG1vc3QgMTAwLiBBZnRlciB0aGF0IHBlciB0ZXN0IGNhc2U6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+b25lIGxpbmUgd2l0aCBhbiBpbnRlZ2VyIHMgKDEgJmxlOyBzICZsZTsgMTAwIDAwMCk6IHRoZSBzdG9jayBwcmljZSBvZiB0aGUgY2FyLjxcL2xpPlxyXG5cdDxsaT5vbmUgbGluZSB3aXRoIGFuIGludGVnZXIgbiAoMCAmbGU7IG4gJmxlOyAxIDAwMCk6IHRoZSBudW1iZXIgb2YgZGlmZmVyZW50IHBhcnRzIHRvIGJlIGluc3RhbGxlZC48XC9saT5cclxuXHQ8bGk+biBsaW5lcyB3aXRoIHR3byBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMgcTxzdWI+aTxcL3N1Yj4gYW5kIHA8c3ViPmk8XC9zdWI+ICgxICZsZTsgcTxzdWI+aTxcL3N1Yj4gJmxlOyAxMDAgYW5kIDEgJmxlOyBwPHN1Yj5pPFwvc3ViPiAmbGU7IDEwIDAwMCk6IGZvciBlYWNoIGRpZmZlcmVudCBwYXJ0IGksIHRoZSBudW1iZXIgb2YgcGllY2VzIHE8c3ViPmk8XC9zdWI+IHJlcXVpcmVkIG9mIHN1Y2ggcGFydCwgYW5kIHRoZSBwcmljZSBwPHN1Yj5pPFwvc3ViPiBmb3IgYSBzaW5nbGUgcGllY2UuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8cD5QZXIgdGVzdCBjYXNlOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPm9uZSBsaW5lIHdpdGggYW4gaW50ZWdlcjogdGhlIHRvdGFsIGFtb3VudCBvZiBtb25leSBuZWVkZWQgdG8gYnV5IHRoZSBjYXIgYW5kIGFsbCB0aGUgcGFydHMuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=