Facebook Hacker Cup: Сила подавляющая

Многие люди в Facebook любят играть в Starcraft II ™. Некоторые из них создали собственную игру с помощью редактора карт Starcraft II ™. В этой игре вы играете за благородных протоссов, защищающих свой родной мир Шакурас от огромной армии зергов. Вы должны нанести зергу как можно больше урона, прежде чем вас разбьют. Вы можете строить только два типа юнитов: генераторы щитов и воинов. Генераторы щитов не наносят урона, но ваша армия выживает в течение одной секунды за каждый созданный вами генератор щита. Воины наносят одно повреждение каждую секунду. После того, как срок действия генераторов щита истечет, ваша армия будет мгновенно захвачена. Сколько генераторов щитов и сколько воинов вы должны построить, чтобы нанести максимальный урон зергу, прежде чем ваша армия будет захвачена? Поскольку протоссы ценят храбрость, если существует более одного решения, вы должны вернуть то, которое использует наибольшее количество воинов.

Ограничения

• 1 ≤ G (стоимость одного генератора щита) ≤ 100
• 1 ≤ W ( стоимость одного воина) ≤ 100
• G + W ≤ M (доступные средства) ≤ 1000000000000 (10 ¹² )