Woburn Challenge 2017-18 Round 2 - Junior Division
Pursued by a swarm of goblins, the members of the Fellowship of the Ring are trying to escape from the Mines of Moria. To do so, they must cross a chasm which is metres wide. The member of the Fellowship can jump a distance of up to metres. Therefore, they can only cross the chasm by themselves if they can jump a distance of at least metres.
Fortunately, if someone is able to jump over the chasm themselves, they can also carry at most one other person along with them. This does not affect their jumping distance. Unfortunately, there isn't enough time for them to then jump back and carry yet another person across.
Assuming that the Fellowship works together, what's the maximum number of its members who can end up getting across the chasm and escaping the Mines of Moria?
Input Specification
The first line of input consists of two space-separated integers, and .
The next line consists of space-separated integers, .
Output Specification
Output a single integer, the maximum number of Fellowship members who can escape.
Sample Input
5 6
3 6 4 1 10
Sample Output
4
Sample Explanation
One optimal strategy is for the member to jump across while carrying the member, and for the member to jump across while carrying the member. Unfortunately, this leaves the member unable to cross by themselves, but there's no way for the entire Fellowship to escape.
Comments