The Epic Battle
The world is again threatened by Captain Nero on the 46th Anniversary of Star Trek.
The great profecy of west land says "A hero trained by great master yoda would rise and fight The tyrant. Only one shall live."
After the completition of the training of the fighter with a few skills. Mastre Yoda has to set a strategy to combine these skills in sequence to do maximum damage, as repeated attack of the same most powerful skill would be too easily anticipated and would do little damage.
For each attack stamina and its damage is known. If the same attack is repeated second time in a row its damage done is only 50 percent of the damage and if done more than two in a row does no damage.
Attacking with same skill with damage v three times in a row leads to a total damage value of 1.5*v.
You have to help Yoda to decide the sequence of the attack that should the fighter take to do maximum damage within the stamina of fighter and leave rest on to 'Queen of Fate'.
The input consists of multiple test cases. Each test case begin with 3 integers in a line.The no of attacks to do k, the no of the different type attacks(different skills) n, and his stamina m.
For each different skill ith line has two integers: the stamina required c and the maximum damage of the attack v.
The end of input would is shown with test case k=m=n=0.
For each output, print the maximum damage value reachable with 1 digit after the decimal point.
If every sequence exceeds the stamina, print only the damage value of 0.0.
2 1 5
3 5 20
3 2 6
0 0 0
Problem Setter : Vivek Keshri