시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 45 25 20 54.054%

문제

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

만약, 팀이 터치 다운(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+XHVhY2JkXHVhZTMwXHVhYzAwIFx1YjA1ZFx1YjA5YyBcdWQ2YzRcdWM1ZDAgXHVjZTVjXHVhZDZjXHViOTdjIFx1YjljY1x1YjA5YyBcdWIzZDlcdWQ2MDFcdWM3NzRcdWIyOTQgJnF1b3Q7XHViMDk4IFx1YzYyNFx1YjI5OCBcdWNkMWQgTlx1YmM4OCBcdWQzMTRcdWFkN2RcdWQ2MDBcdWQzYjRcdWFlMzBcdWI5N2MgXHVkNTg4XHVjNWI0ISZxdW90OyBcdWI3N2NcdWFjZTAgXHVjNzkwXHViNzkxXHVkNTg4XHViMmU0LiBOXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YjNkOVx1ZDYwMVx1Yzc3NFx1YWMwMCBcdWM3NTFcdWM2ZDBcdWQ1NThcdWIyOTQgXHVkMzAwXHVjNzc0IFx1YjRkZFx1YzgxMFx1ZDU1YyBcdWM4MTBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWM4MTBcdWMyMThcdWFjMDAgXHVjNWVjXHViN2VjXHVhYzAwXHVjOWMwXHViNzdjXHViYTc0LCBcdWFjMDBcdWM3YTUgXHVkMDcwIFx1YWMxMlx1Yzc0NCBcdWFkNmNcdWQ1NWNcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1YjNkOVx1ZDYwMVx1Yzc3NFx1YWMwMCBcdWQzMTRcdWFkN2RcdWQ2MDBcdWQzYjRcdWFlMzBcdWI5N2MgMjlcdWJjODggXHVkNTg4XHViMmU0XHViYTc0LCBcdWQzMDBcdWM3NDAgMywgMiwgMiwgN1x1YzgxMCBcdWNkMWQgMTRcdWM4MTBcdWM3NDQgXHViNGRkXHVjODEwXHVkNTVjIFx1YWM4M1x1Yzc3NCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVjODEwXHVjMjE4IFx1YzkxMVx1YzVkMFx1YzExYyBcdWNkNWNcdWIzMDBcdWFjMTJcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgXHVjNzc0IFx1YWMxMlx1Yzc0MCAxXHVhY2ZjIDIwXHVjNzQ0IFx1ZDNlY1x1ZDU2OFx1ZDU1OFx1YjI5NCBcdWFkZjggXHVjMGFjXHVjNzc0XHVjNzU4IFx1YWMxMlx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHViNDUwIFx1YzgxNVx1YzIxOCBOXHVhY2ZjIE0gKDEgJmxlOyBOICZsZTsgNSwwMDAsIDEgJmxlOyBNICZsZTsgMTApIFx1YzczY1x1Yjg1YyBcdWMyZGNcdWM3OTFcdWQ1NThcdWJhNzAsIE5cdWM3NDAgXHViM2Q5XHVkNjAxXHVjNzc0XHVhYzAwIFx1ZDU1YyBcdWQzMTRcdWFkN2RcdWQ2MDBcdWQzYjRcdWFlMzBcdWM3NTggXHVkNjlmXHVjMjE4LCBNXHVjNzQwIFx1YWRmOCBcdWFjYmRcdWFlMzBcdWM1ZDBcdWMxMWMgXHViMDk4XHVjNjJjIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViNGRkXHVjODEwXHVjNzU4IFx1Yzg4NVx1Yjk1OFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE1cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFM8c3ViPmk8XC9zdWI+ICgxICZsZTsgUzxzdWI+aTxcL3N1Yj4gJmxlOyAyMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwLCBcdWFjMDFcdWFjMDFcdWM3NTggXHVhYzEyXHVjNzQwIFx1YWRmOCBcdWFjYmRcdWFlMzBcdWM1ZDBcdWMxMWMgXHVkMzAwXHVjNzc0IFx1ZDU1YyBcdWJjODhcdWM1ZDAgXHViNGRkXHVjODEwXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjODEwXHVjMjE4XHVjNzc0XHViMmU0LiBcdWJhYThcdWI0ZTAgXHVjODEwXHVjMjE4XHViMjk0IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxXHVhYzAxXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWIzZDlcdWQ2MDFcdWM3NzRcdWFjMDAgXHVjNzUxXHVjNmQwXHVkNTU4XHViMjk0IFx1ZDMwMFx1Yzc3NCBcdWI0ZGRcdWM4MTBcdWQ1NWMgXHVjODEwXHVjMjE4XHVjNzU4IFx1Y2Q1Y1x1YjMwMFx1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCwgXHViZDg4XHVhYzAwXHViMmE1XHVkNTVjIFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCAtMVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTA1NjQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQdXNodXBzIiwiZGVzY3JpcHRpb24iOiI8cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXMyXC9wdXNodXAucG5nXCIgc3R5bGU9XCJoZWlnaHQ6ODVweDsgd2lkdGg6MTcwcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+QSBmcmllbmQgb2YgeW91cnMgaXMgb24gdGhlIGNoZWVyIHNxdWFkIGZvciB0aGVpciBmb290YmFsbCB0ZWFtLiBFYWNoIHRpbWUgdGhlIHRlYW0gc2NvcmVzLCB0aGUgY2hlZXIgc3F1YWQgZG9lcyBwdXNodXBzJm1kYXNoO29uZSBmb3IgZWFjaCBwb2ludCB0aGUgdGVhbSBoYXMgc2NvcmVkIHNvIGZhci4gSWYgdGhlIHRlYW1zIHNjb3JlcyBhIHRvdWNoZG93biAoNyBwb2ludHMpLCB0aGUgc3F1YWQgZG9lcyA3IHB1c2h1cHMuIElmIHRoZSB0ZWFtIHRoZW4gc2NvcmVzIGEgZmllbGQgZ29hbCAoMyBwb2ludHMpLCB0aGUgY2hlZXIgc3F1YWQgZG9lcyAxMCBwdXNodXBzLiBJZiB0aGUgdGVhbSB0aGVuIHNjb3JlcyBhIHNhZmV0eSAoMiBwb2ludHMpLCB0aGUgc3F1YWQgd2lsbCBkbyAxMiBwdXNodXBzLiBBdCB0aGUgZW5kIG9mIHRoYXQgZ2FtZSwgdGhlIHNxdWFkIHdpbGwgZW5kIHVwIGhhdmluZyBkb25lIDcrMTArMTI9MjkgcHVzaHVwcyE8XC9wPlxyXG5cclxuPHA+WW91IG1lZXQgeW91ciBmcmllbmQgYWZ0ZXIgYSBnYW1lLCBhbmQgdGhleSBzYXkgJmxkcXVvO0JveSwgYW0gSSB0aXJlZCEgSSBkaWQgYSB0b3RhbCBvZiBuIHB1c2h1cHMgYXQgdGhlIGdhbWUgdG9kYXkhJnJkcXVvOyBhbmQgcHJvbXB0bHkgY29sbGFwc2UgZnJvbSBleGhhdXN0aW9uLiBHaXZlbiBuLCB0aGUgbnVtYmVyIG9mIHB1c2h1cHMsIGNhbiB5b3UgZmlndXJlIG91dCBob3cgdGhlIHRlYW0gc2NvcmVkPyBNb3JlIHRoYW4gb25lIHNjb3JlIG1heSBiZSBwb3NzaWJsZS4gRm9yIGV4YW1wbGUsIGZvciAyOSBwdXNodXBzLCB0aGUgdGVhbSBjb3VsZCBoYXZlIHNjb3JlZCAzLCB0aGVuIDIsIHRoZW4gMiwgdGhlbiA3LCBmb3IgYSB0b3RhbCBvZiAxNCBwb2ludHMuIElmIHNvLCBmaW5kIHRoZSBoaWdoZXN0IHBvc3NpYmxlIHNjb3JlLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IHdpbGwgc3RhcnQgd2l0aCBhIHNpbmdsZSBudW1iZXIgb24gdGhlIGZpcnN0IGxpbmUgZ2l2aW5nIHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcywgYmV0d2VlbiAxIGFuZCAyMCwgaW5jbHVzaXZlLiBFYWNoIHRlc3QgY2FzZSB3aWxsIGJlZ2luIHdpdGggdHdvIGludGVnZXJzIE4gYW5kIE0gMSAmbGU7IE4gJmxlOyA1LDAwMCwgMSAmbGU7IE0gJmxlOyAxMCB3aGVyZSBOIGlzIHRoZSBudW1iZXIgb2YgcHVzaHVwcyB0aGUgY2hlZXIgc3F1YWQgZGlkLCBhbmQgTSBpcyB0aGUgbnVtYmVyIG9mIHdheXMgYSB0ZWFtIGNhbiBzY29yZSBwb2ludHMgaW4gdGhhdCBzcG9ydC4gT24gdGhlIG5leHQgbGluZSB3aWxsIGJlIE0gdW5pcXVlIGludGVnZXJzIFNpLCAxICZsZTsgU2kgJmxlOyAyMCwgd2l0aCBhIHNpbmdsZSBzcGFjZSBiZXR3ZWVuIHRoZW0sIGluZGljYXRpbmcgdGhlIG51bWJlciBvZiBwb2ludHMgdGhlIHRlYW0gZ2V0cyBmb3IgZWFjaCBraW5kIG9mIHNjb3JlLiBUaGUgc2NvcmVzIGFyZSBpbmRlcGVuZGVudDsgYSB0ZWFtIGNhbiBhY2NydWUgc2NvcmVzIGluIGFueSBvcmRlci48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIG91dHB1dCBhIHNpbmdsZSBpbnRlZ2VyIGluZGljYXRpbmcgdGhlIHRlYW0mcnNxdW87cyBmaW5hbCBzY29yZS4gSWYgbW9yZSB0aGFuIG9uZSBmaW5hbCBzY29yZSBjYW4gbGVhZCB0byB0aGUgZ2l2ZW4gbnVtYmVyIG9mIHB1c2h1cHMsIG91dHB1dCB0aGUgbGFyZ2VzdCBvbmUuIElmIG5vIGZpbmFsIHNjb3JlIGNhbiBsZWFkIHRvIHRoZSBnaXZlbiBudW1iZXIgb2YgcHVzaHVwcywgdGhlbiB5b3VyIGZyaWVuZCBtdXN0IGhhdmUgbWlzY291bnRlZC4gSW4gdGhpcyBjYXNlLCBvdXRwdXQgJmxzcXVvOy0xJnJzcXVvOy4gT3V0cHV0IG5vIGV4dHJhIHNwYWNlcy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=