FP - Finding password
Bom has a list of n favorite numbers which are birthday, driving license, passport number, etc After creating an email account, Bom wants to choose a password as the largest number P among all possible numbers generated by the combinations of k (1 <= k <= n) positive numbers in the favorite list so that P is divisible by 9.
Your task is writing a program to help find P the password for Bom’s email.
Input
The first line contains a positive integer T as the number of test cases in the input file. The following lines describe information of each test case including:
- One line containing two positive integers n and k,
- n following lines are n favorite numbers.
Output
The output file contains T lines; each line is the solution of the corresponding test case that is either password P or -1 in case of not finding a feasible number.
Limits
T <= 30
1 <= k <= n <= 100
1 <= all favorite numbers <= 10^6
Example
Input: 2 3 2 1 2 3 5 2 1 2 3 4 5 Output: -1 54
Added by: | sieunhan |
Date: | 2009-11-29 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 NODEJS OBJC PERL6 SQLITE VB.NET |
Resource: | Do Duc Dong - ACM Vietnam Practice |