All Submissions


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'.

Input

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.

Constraints

  • 1<=k<=20
  • 1<=n<=50
  • 1<=m<=100
  • 1<=c<=50
  • 1<=v<=10000


Output

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.

Sample Input


2 1 5
3 5
3 5 20
2 5
18 6
1 1
3 3
2 3
3 2 6
7 10
2 10
0 0 0


Sample Output


0.0
13.0
15.0


Problem Setter : Vivek Keshri

Languages: C,C++,Java

Time Limit: 1 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Submit

Login to post clarification.

No Clarifications.

Contest

Mode Judge

Passive

Online

Overall Rankings

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0