LOTR1 - Helms Deep
We have all heard about good triumphing over evil. A perfect example would be the Battle of Helms Deep.
Lets probe a little deeper...
The people (especially warriors) of Rohan (good side) could not have known that they would win the battle before it was actually fought. This would have forced them to think up of some other alternate means of escape. A river flows near the fortress and naturally, they think this to be the best escape route. They build the biggest ship possible with the available materials.
This ship can carry a total weight of W (0 < W < 10^9) kilograms. There are a total of n (0 < n < 10000) people at Helms Deep having weights wi (0 < wi < 10^9).
What is the maximum number of people who can escape?
Input
1st line contains t, the number of testcases. First line of each test case contains the number of people n(0 One line giving the maximum number of people who can escape.Output
Example
Input:
1
3 3
2
1
3
Output:
2
Added by: | pradeep |
Date: | 2009-06-15 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
Resource: | Lord of the Rings (2 towers) |