The final exams are approaching, and the underachievers are scrambling to study. Generally speaking, not studying for the whole semester and trying to cram at the last minute is of little use, but if you make reasonable use of this final period for review, there is a certain probability of a comeback.

There are $N$ courses to review this semester. Each course has a maximum score of $M_i$, and you have an initial exam score of $B_i$ (after all, you learned a little bit during the semester). Each course also has a credit value $W_i$.

There are $D$ days left, and you can only review one course per day. Reviewing a course on a given day will increase your final exam score by $P_i$. The final exam score cannot exceed the maximum score; if reviewing causes the score to exceed the maximum, it will simply become the maximum score and go no higher.

One difference between an underachiever and a top student is memory. If an underachiever does not review, they will forget, and as the time without review increases, the rate of forgetting becomes faster and faster. If you have already gone $k-1$ consecutive days without reviewing a course, then on the $k$-th day, not reviewing it will cause your final exam score for that subject to drop by $S_i + k \cdot T_i$. Assume that you reviewed all subjects on the day before these $D$ days, meaning the "consecutive days without review" $k$ for each course starts from 0.

The final exam score will not drop below 0. If forgetting causes the score to drop below 0, it will simply become 0 and go no lower.

If your final exam score for a subject is lower than $F_i$, you are considered to have failed that course. Although you are an underachiever, you are an underachiever with principles, so you do not allow any failures.

Assuming the final exam score for each course is $G_i$, your total grade point average for this semester is: $$\sum_{i=1}^{N} W_i \left(1 - \left(\frac{M_i - G_i}{M_i}\right)^2\right)$$

In short, the final grade for each course $1 - (\frac{M_i - G_i}{M_i})^2$ is determined by the final exam score and the maximum score, and the final grade is between 0 and 1. The total grade point average is the weighted sum of the final grades of each course, where the weights are the credits $W_i$.

Now, please formulate a study plan to maximize the total grade point average without failing any courses.

Input

The input files are xuezha1.in~xuezha10.in. The first line of the input contains two non-negative integers $N, D$. The next $N$ lines each contain a string of length no more than 60 consisting only of English letters (representing the course name) and seven integers $M_i, B_i, P_i, S_i, T_i, F_i, W_i$. Each value is separated by a space. The data guarantees that there exists at least one plan where no course is failed.

Output

For each input file, you need to submit an output file xuezha1.out~xuezha10.out. The content of the output file should contain no more than $D$ lines, each line containing a string representing the course studied on that day. If the output contains fewer than $D$ lines, we consider this to be a study plan for the first few days, and nothing is reviewed for the remaining days.

Examples

Input 1

4 5
Chinese 150 150 141 1 10 1 90
Math 150 150 135 12 5 2 90
English 120 120 118 15 7 1 70
Others 300 300 287 20 18 1 180

Output 1

Math
Math
Others
Chinese
Others

Note

The provided output is not the optimal solution for the example; it is provided only for format reference.

Scoring

Each test case has a reference grade point average $Best$, and your grade point average is $Ans$. If your plan is invalid, you will receive 0 points. If $Ans > Best$, you will receive 10 points. Otherwise, you will receive $\max \left\{1, \left\lfloor 10 \left( \max \left\{0, 1 - \frac{Best - Ans}{N} \right\} \right)^2 \right\rfloor \right\}$ points.