Bag of fake money#170
There are bags of coins, numbered from to . The number of coins in each bag is written on it. Exactly one bag contains only counterfeit coins. In all other bags, every coin is genuine.
A genuine coin weighs grams, while a counterfeit coin weighs grams. You have a scale that shows the total weight of the coins placed upon it. Find the minimum number of weighings required to guarantee determination of the bag containing only counterfeit coins, in the worst case. You may take any number of coins from any bag, and you may keep track of which bag each coin came from.
The first line contains (1 \leq n \leq 30000) — the number of bags. Each of the following lines contains an integer representing the number of coins in that bag. Each number is between and .
Print one integer — the minimum possible number of weighings.
Example 1