The CS Nerd is dreaming about giving Christmas presents to the girl. Unfortunately, he does not have enough courage to do this in real life.
In the dream, there are presents that he could possibly give to the girl. The present has a weight of . The CS Nerd wants to impress the girl by building a large stack of presents – that is, presents stacked one on top of each other – and giving it to her.
However, the CS Nerd needs to ensure that the sum of the weights of the presents above any present does not exceed that present's weight. What is the maximum number of presents that can be in the stack?
The first line of input will contain a single integer .
lines of input follow. The line will consist of a single integer, .
For 20% of the points, .
For an additional 30% of the points, .
Output a single integer, the maximum possible number of presents that can be in the stack.
5 7 8 2 5 10
Explanation for Sample Output
The CS Nerd can stack presents in the order , , and from the bottom. The weights of these presents are , , and , respectively. Note that this is not the only possible solution.