Description

A fuel station has infinite amount of each of N kinds of fuel. Each kind of fuel has density a ~i~ , cost b~i~ and intensity c ~i~ . m kilograms of such fuel has volume ma ~i~ , intensity mc~i~ and costs mb~i~ dollars. Your car can store any mixture of different kinds of fuel such that the overall volume does not exceed A . You have B dollars. Your task is to determine the maximal overall intensity of the fuel you can buy. Note that you can buy any nonnegative amount of any kind of fuel, not necessarily an integer number of kilograms.

Input

The first line of the input contains three integers N , A , B (1≤ N ≤ 100000, 1≤ A , B ≤ 1000). Each of the next N lines describes one kind of fuel. i +1-st line contains three integers a ~i~ , b ~i~ , c~i~ (0~ i ,b ~i~ ,c ~i~ ≤ 1000).~~

~

Output

The first line of the input contains three integers N , A , B (1≤ N ≤ 100000, 1≤ A , B ≤ 1000). Each of the next N lines describes one kind of fuel. i +1-st line contains three integers a ~i~ , b ~i~ , c~i~ (0~ i ,b ~i~ ,c ~i~ ≤ 1000).~~

~

Samples

2 3 3
1 2 1
2 1 1

2.000

Limitation

A,B均大于0,小于等于100000 Ai,Bi,Ci均大于0小于等于1000 50%数据N小于等于100 100%数据N小于等于100000