Time Limit: 1000 mSec
Memory Limit: 32768 KB
May 9 this year, More than 50 heads of states or international organizations gathered on Moscow to commemorate the 60th anniversary of the end of World War II. Battle of Stalingrad from July to November in 1942 was the turning point in World War II. Soviets troops used bazooka in this battle first time, and made good execution for heinie. For there having a Russian letter "K" in the bazooka, soviet soldiers named the bazooka Katyusha rocket. The theory of Katyusha rocket is that a group rockets is fired at the same area, in order to make dense blast and good execution swiftly.
Suppose that you can manipulate a Katyusha rocket, which can be moved westward or eastward, to assault the enemy in the northern area. Commander has numbered each kind of enemy objects (soldier, armored car, tank etc.). The higher of an object value is, the greater number the object has. The attack is carried out in the following way:
1. Katyusha rocket can only move eastward or westward along x axes.
2. Given the cannon-shot and the blast radius of the bazooka each time, you must choose a launch position where you can destroy enemy objects with the total value as high as possible.
3. Katyusha rocket can only be fired northward.
4. The radius of bombsite is r. All objects within bombsite will be destroyed.
5. At the moment that a few bombsites include the same total value of enemy objects, exterminate the west objects first.