시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 53 27 22 51.163%

문제

동혁이는 미식축구를 보면서 팔굽혀펴기를 하고 있다. 동혁이는 자신이 응원하는 팀이 득점을 성공할 때 마다 팀이 득점한 점수만큼 팔굽혀펴기를 한다.

만약, 팀이 터치 다운(7점)을 했다면 총 7번 팔굽혀펴기를 해야 하고, 그 다음에 필드 골(3점)을 했다면, 팔굽혀펴기를 10번 해야 한다. 그 다음 세이프티(2점)을 했다면, 이제 팔굽혀펴기를 12번 해야 한다. 만약, 이 상태에서 게임이 끝났다면, 동혁이는 게임을 보는 동안 7+10+12=29번 팔굽혀펴기를 한 것이다.

경기가 끝난 후에 친구를 만난 동혁이는 "나 오늘 총 N번 팔굽혀펴기를 했어!" 라고 자랑했다. N이 주어졌을 때, 동혁이가 응원하는 팀이 득점한 점수를 구하는 프로그램을 작성하시오. 가능한 점수가 여러 가지라면, 가장 큰 값을 구한다. 예를 들어, 동혁이가 팔굽혀펴기를 29번 했다면, 팀은 3, 2, 2, 7점 총 14점을 득점한 것이 가능한 점수 중에서 최댓값이다.

입력

첫째 줄에 테스트 케이스의 개수가 주어지며, 이 값은 1과 20을 포함하는 그 사이의 값이다.

각 테스트 케이스는 두 정수 N과 M (1 ≤ N ≤ 5,000, 1 ≤ M ≤ 10) 으로 시작하며, N은 동혁이가 한 팔굽혀펴기의 횟수, M은 그 경기에서 나올 수 있는 득점의 종류이다.

다음 M개의 줄에는 Si (1 ≤ Si ≤ 20)가 주어지며, 각각의 값은 그 경기에서 팀이 한 번에 득점할 수 있는 점수이다. 모든 점수는 서로 다르다.

출력

각각의 테스트 케이스에 대해서, 동혁이가 응원하는 팀이 득점한 점수의 최댓값을 출력한다. 만약, 불가능한 경우에는 -1을 출력한다.

예제 입력 1

4
29 3
7 3 2
15 1
1
16 1
1
6 2
3 1

예제 출력 1

14
5
-1
3
W3sicHJvYmxlbV9pZCI6IjEwNTY0IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVkMzE0XHVhZDdkXHVkNjAwXHVkM2I0XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzMlwvcHVzaHVwLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0Ojg1cHg7IHdpZHRoOjE3MHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YjNkOVx1ZDYwMVx1Yzc3NFx1YjI5NCBcdWJiZjhcdWMyZGRcdWNkOTVcdWFkNmNcdWI5N2MgXHViY2Y0XHViYTc0XHVjMTFjIFx1ZDMxNFx1YWQ3ZFx1ZDYwMFx1ZDNiNFx1YWUzMFx1Yjk3YyBcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWIzZDlcdWQ2MDFcdWM3NzRcdWIyOTQgXHVjNzkwXHVjMmUwXHVjNzc0IFx1Yzc1MVx1YzZkMFx1ZDU1OFx1YjI5NCBcdWQzMDBcdWM3NzQgXHViNGRkXHVjODEwXHVjNzQ0IFx1YzEzMVx1YWNmNVx1ZDU2MCBcdWI1NGMgXHViOWM4XHViMmU0IFx1ZDMwMFx1Yzc3NCBcdWI0ZGRcdWM4MTBcdWQ1NWMgXHVjODEwXHVjMjE4XHViOWNjXHVkMDdjIFx1ZDMxNFx1YWQ3ZFx1ZDYwMFx1ZDNiNFx1YWUzMFx1Yjk3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjljY1x1YzU3ZCwgXHVkMzAwXHVjNzc0IFx1ZDEzMFx1Y2U1OCBcdWIyZTRcdWM2YjQoN1x1YzgxMClcdWM3NDQgXHVkNTg4XHViMmU0XHViYTc0IFx1Y2QxZCA3XHViYzg4IFx1ZDMxNFx1YWQ3ZFx1ZDYwMFx1ZDNiNFx1YWUzMFx1Yjk3YyBcdWQ1NzRcdWM1N2MgXHVkNTU4XHVhY2UwLCBcdWFkZjggXHViMmU0XHVjNzRjXHVjNWQwIFx1ZDU0NFx1YjRkYyBcdWFjZTgoM1x1YzgxMClcdWM3NDQgXHVkNTg4XHViMmU0XHViYTc0LCBcdWQzMTRcdWFkN2RcdWQ2MDBcdWQzYjRcdWFlMzBcdWI5N2MgMTBcdWJjODggXHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YyBcdWMxMzhcdWM3NzRcdWQ1MDRcdWQyZjAoMlx1YzgxMClcdWM3NDQgXHVkNTg4XHViMmU0XHViYTc0LCBcdWM3NzRcdWM4MWMgXHVkMzE0XHVhZDdkXHVkNjAwXHVkM2I0XHVhZTMwXHViOTdjIDEyXHViYzg4IFx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCwgXHVjNzc0IFx1YzBjMVx1ZDBkY1x1YzVkMFx1YzExYyBcdWFjOGNcdWM3ODRcdWM3NzQgXHViMDVkXHViMGFjXHViMmU0XHViYTc0LCBcdWIzZDlcdWQ2MDFcdWM3NzRcdWIyOTQgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1YmNmNFx1YjI5NCBcdWIzZDlcdWM1NDggNysxMCsxMj0yOVx1YmM4OCBcdWQzMTRcdWFkN2RcdWQ2MDBcdWQzYjRcdWFlMzBcdWI5N2MgXHVkNTVjIFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhY2JkXHVhZTMwXHVhYzAwIFx1YjA1ZFx1YjA5YyBcdWQ2YzRcdWM1ZDAgXHVjZTVjXHVhZDZjXHViOTdjIFx1YjljY1x1YjA5YyBcdWIzZDlcdWQ2MDFcdWM3NzRcdWIyOTQgJnF1b3Q7XHViMDk4IFx1YzYyNFx1YjI5OCBcdWNkMWQgTlx1YmM4OCBcdWQzMTRcdWFkN2RcdWQ2MDBcdWQzYjRcdWFlMzBcdWI5N2MgXHVkNTg4XHVjNWI0ISZxdW90OyBcdWI3N2NcdWFjZTAgXHVjNzkwXHViNzkxXHVkNTg4XHViMmU0LiBOXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YjNkOVx1ZDYwMVx1Yzc3NFx1YWMwMCBcdWM3NTFcdWM2ZDBcdWQ1NThcdWIyOTQgXHVkMzAwXHVjNzc0IFx1YjRkZFx1YzgxMFx1ZDU1YyBcdWM4MTBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWM4MTBcdWMyMThcdWFjMDAgXHVjNWVjXHViN2VjIFx1YWMwMFx1YzljMFx1Yjc3Y1x1YmE3NCwgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWFjMTJcdWM3NDQgXHVhZDZjXHVkNTVjXHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWIzZDlcdWQ2MDFcdWM3NzRcdWFjMDAgXHVkMzE0XHVhZDdkXHVkNjAwXHVkM2I0XHVhZTMwXHViOTdjIDI5XHViYzg4IFx1ZDU4OFx1YjJlNFx1YmE3NCwgXHVkMzAwXHVjNzQwIDMsIDIsIDIsIDdcdWM4MTAgXHVjZDFkIDE0XHVjODEwXHVjNzQ0IFx1YjRkZFx1YzgxMFx1ZDU1YyBcdWFjODNcdWM3NzQgXHVhYzAwXHViMmE1XHVkNTVjIFx1YzgxMFx1YzIxOCBcdWM5MTFcdWM1ZDBcdWMxMWMgXHVjZDVjXHViMzEzXHVhYzEyXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIFx1Yzc3NCBcdWFjMTJcdWM3NDAgMVx1YWNmYyAyMFx1Yzc0NCBcdWQzZWNcdWQ1NjhcdWQ1NThcdWIyOTQgXHVhZGY4IFx1YzBhY1x1Yzc3NFx1Yzc1OCBcdWFjMTJcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YjQ1MCBcdWM4MTVcdWMyMTggTlx1YWNmYyBNICgxICZsZTsgTiAmbGU7IDUsMDAwLCAxICZsZTsgTSAmbGU7IDEwKSBcdWM3M2NcdWI4NWMgXHVjMmRjXHVjNzkxXHVkNTU4XHViYTcwLCBOXHVjNzQwIFx1YjNkOVx1ZDYwMVx1Yzc3NFx1YWMwMCBcdWQ1NWMgXHVkMzE0XHVhZDdkXHVkNjAwXHVkM2I0XHVhZTMwXHVjNzU4IFx1ZDY5Zlx1YzIxOCwgTVx1Yzc0MCBcdWFkZjggXHVhY2JkXHVhZTMwXHVjNWQwXHVjMTFjIFx1YjA5OFx1YzYyYyBcdWMyMTggXHVjNzg4XHViMjk0IFx1YjRkZFx1YzgxMFx1Yzc1OCBcdWM4ODVcdWI5NThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBNXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBTPHN1Yj5pPFwvc3ViPiAoMSAmbGU7IFM8c3ViPmk8XC9zdWI+ICZsZTsgMjApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YWMxMlx1Yzc0MCBcdWFkZjggXHVhY2JkXHVhZTMwXHVjNWQwXHVjMTFjIFx1ZDMwMFx1Yzc3NCBcdWQ1NWMgXHViYzg4XHVjNWQwIFx1YjRkZFx1YzgxMFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzgxMFx1YzIxOFx1Yzc3NFx1YjJlNC4gXHViYWE4XHViNGUwIFx1YzgxMFx1YzIxOFx1YjI5NCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHViM2Q5XHVkNjAxXHVjNzc0XHVhYzAwIFx1Yzc1MVx1YzZkMFx1ZDU1OFx1YjI5NCBcdWQzMDBcdWM3NzQgXHViNGRkXHVjODEwXHVkNTVjIFx1YzgxMFx1YzIxOFx1Yzc1OCBcdWNkNWNcdWIzMTNcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QsIFx1YmQ4OFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgLTFcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjEwNTY0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUHVzaHVwcyIsImRlc2NyaXB0aW9uIjoiPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzMlwvcHVzaHVwLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0Ojg1cHg7IHdpZHRoOjE3MHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkEgZnJpZW5kIG9mIHlvdXJzIGlzIG9uIHRoZSBjaGVlciBzcXVhZCBmb3IgdGhlaXIgZm9vdGJhbGwgdGVhbS4gRWFjaCB0aW1lIHRoZSB0ZWFtIHNjb3JlcywgdGhlIGNoZWVyIHNxdWFkIGRvZXMgcHVzaHVwcyZtZGFzaDtvbmUgZm9yIGVhY2ggcG9pbnQgdGhlIHRlYW0gaGFzIHNjb3JlZCBzbyBmYXIuIElmIHRoZSB0ZWFtcyBzY29yZXMgYSB0b3VjaGRvd24gKDcgcG9pbnRzKSwgdGhlIHNxdWFkIGRvZXMgNyBwdXNodXBzLiBJZiB0aGUgdGVhbSB0aGVuIHNjb3JlcyBhIGZpZWxkIGdvYWwgKDMgcG9pbnRzKSwgdGhlIGNoZWVyIHNxdWFkIGRvZXMgMTAgcHVzaHVwcy4gSWYgdGhlIHRlYW0gdGhlbiBzY29yZXMgYSBzYWZldHkgKDIgcG9pbnRzKSwgdGhlIHNxdWFkIHdpbGwgZG8gMTIgcHVzaHVwcy4gQXQgdGhlIGVuZCBvZiB0aGF0IGdhbWUsIHRoZSBzcXVhZCB3aWxsIGVuZCB1cCBoYXZpbmcgZG9uZSA3KzEwKzEyPTI5IHB1c2h1cHMhPFwvcD5cclxuXHJcbjxwPllvdSBtZWV0IHlvdXIgZnJpZW5kIGFmdGVyIGEgZ2FtZSwgYW5kIHRoZXkgc2F5ICZsZHF1bztCb3ksIGFtIEkgdGlyZWQhIEkgZGlkIGEgdG90YWwgb2YgbiBwdXNodXBzIGF0IHRoZSBnYW1lIHRvZGF5ISZyZHF1bzsgYW5kIHByb21wdGx5IGNvbGxhcHNlIGZyb20gZXhoYXVzdGlvbi4gR2l2ZW4gbiwgdGhlIG51bWJlciBvZiBwdXNodXBzLCBjYW4geW91IGZpZ3VyZSBvdXQgaG93IHRoZSB0ZWFtIHNjb3JlZD8gTW9yZSB0aGFuIG9uZSBzY29yZSBtYXkgYmUgcG9zc2libGUuIEZvciBleGFtcGxlLCBmb3IgMjkgcHVzaHVwcywgdGhlIHRlYW0gY291bGQgaGF2ZSBzY29yZWQgMywgdGhlbiAyLCB0aGVuIDIsIHRoZW4gNywgZm9yIGEgdG90YWwgb2YgMTQgcG9pbnRzLiBJZiBzbywgZmluZCB0aGUgaGlnaGVzdCBwb3NzaWJsZSBzY29yZS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCB3aWxsIHN0YXJ0IHdpdGggYSBzaW5nbGUgbnVtYmVyIG9uIHRoZSBmaXJzdCBsaW5lIGdpdmluZyB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMsIGJldHdlZW4gMSBhbmQgMjAsIGluY2x1c2l2ZS4gRWFjaCB0ZXN0IGNhc2Ugd2lsbCBiZWdpbiB3aXRoIHR3byBpbnRlZ2VycyBOIGFuZCBNIDEgJmxlOyBOICZsZTsgNSwwMDAsIDEgJmxlOyBNICZsZTsgMTAgd2hlcmUgTiBpcyB0aGUgbnVtYmVyIG9mIHB1c2h1cHMgdGhlIGNoZWVyIHNxdWFkIGRpZCwgYW5kIE0gaXMgdGhlIG51bWJlciBvZiB3YXlzIGEgdGVhbSBjYW4gc2NvcmUgcG9pbnRzIGluIHRoYXQgc3BvcnQuIE9uIHRoZSBuZXh0IGxpbmUgd2lsbCBiZSBNIHVuaXF1ZSBpbnRlZ2VycyBTaSwgMSAmbGU7IFNpICZsZTsgMjAsIHdpdGggYSBzaW5nbGUgc3BhY2UgYmV0d2VlbiB0aGVtLCBpbmRpY2F0aW5nIHRoZSBudW1iZXIgb2YgcG9pbnRzIHRoZSB0ZWFtIGdldHMgZm9yIGVhY2gga2luZCBvZiBzY29yZS4gVGhlIHNjb3JlcyBhcmUgaW5kZXBlbmRlbnQ7IGEgdGVhbSBjYW4gYWNjcnVlIHNjb3JlcyBpbiBhbnkgb3JkZXIuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBvdXRwdXQgYSBzaW5nbGUgaW50ZWdlciBpbmRpY2F0aW5nIHRoZSB0ZWFtJnJzcXVvO3MgZmluYWwgc2NvcmUuIElmIG1vcmUgdGhhbiBvbmUgZmluYWwgc2NvcmUgY2FuIGxlYWQgdG8gdGhlIGdpdmVuIG51bWJlciBvZiBwdXNodXBzLCBvdXRwdXQgdGhlIGxhcmdlc3Qgb25lLiBJZiBubyBmaW5hbCBzY29yZSBjYW4gbGVhZCB0byB0aGUgZ2l2ZW4gbnVtYmVyIG9mIHB1c2h1cHMsIHRoZW4geW91ciBmcmllbmQgbXVzdCBoYXZlIG1pc2NvdW50ZWQuIEluIHRoaXMgY2FzZSwgb3V0cHV0ICZsc3F1bzstMSZyc3F1bzsuIE91dHB1dCBubyBleHRyYSBzcGFjZXMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d