The intergalactic financial crisis is hitting hard. In these poor economic times, income from your droid-trading business on Tattooine is barely enough to survive on. You have heard, though, that there is a huge market for human-horn on the planet Xenu. After extensive ethical deliberations, you have decided to take your spaceship Serenity to the planet Earth (which is mostly harmless) and poach some quality human, a serious crime in The Federation.
The transporter beam on your spaceship is capable of instantly abducting all humans in a region W metres wide. Conveniently, the humans of Earth are standing in a long line. You are given the distance of each human from the start of the line, and the width in metres of your transporter beam. Before conducting your devious money-making operation, you wish to write a program to determine the maximum number of humans specimens you can collect with your transporter beam. You only have one chance to use your beam before the intergalactic police begin pursuit. Note that a human must be entirely contained by the beam to be successfully abducted (for example, with a beam of width 5 metres you can not abduct two humans standing exactly 5 metres apart).
To evaluate your solution, the judges will run your program against several different input files. All of these files will adhere to the following bounds:
As some of the test cases will be quite large, you may need to think about how well your solution scales for larger input values. However, not all the cases will be large - in particular:
Your program should read from the file . The first line of this file will contain two space-separated integers N and W. The following N lines of input will each contain one integer pi: the distance of the ith human from the start of the line.
Your program should write to the file . Your output file should contain one line with one integer: the maximum number of humans you can abduct with your beam.
8 4 3 4 7 9 10 20 22 25
In this example, there are eight humans and your beam has width 4. You can collect three humans by abducting those at positions 7, 9 and 10. This is the largest number possible. Note that your beam is not large enough to collect the three at 3, 4 and 7.
6 10 5 9 12 15 17 30
In this example, there are only six humans and your beam has a width of 10. You can collect four humans by abducting those at positions 9, 12, 15 and 17.
The score for each input scenario will be 100% if the correct answer is written to the output file, and 0% otherwise.