Problem F
Vinnuálag

Knowing all you do now about the ÁFLV course you think to yourself how much effort you would have had to exert, had you worked the same amount every week of the course? That’s exactly what we’ll consider here. To clarify, same effort every week means equally many seconds are spent working on course projects every week.

Each week projects are assigned, and since the course is over you know how many seconds each project takes to finish. Each project gives some number of points and each week has a value $s$ which says how many points are needed to get a perfect $10$. If you get less than $s$ points, the grade is calculated as $10 \cdot (1 - (1 - x/s)^2)$ where $x$ are the number of points gotten. We will also assume that the projects are always completed in the order they are given. Half-finished projects give no points.

Furthermore only the $k$ best grades out of $n$ count for the final grade, and each week has equal weight. The weeks count for $75\% $ of the final grade, against a $25\% $ exam. To be safe we want the find the level of effort that makes the project grade at least $4.75$ to get a pass even with the minimal passing exam score.

Thus the question is now, how many seconds a week do you need?

1 Input

The first line of input contains integers $n$ and $1 \leq k \leq n$, the number of weeks in the course and how many weeks count for the final grade. Next there are $3n$ lines, each three lines describing one week. The first line contains two integers $0 \leq s \leq 10^9$ and $m$, where $s$ is the score needed to get a $10$ that week and $m$ is the number of projects assigned that week. The next line contains $m$ integers $0 \leq t_ i \leq 10\, 000$, the number of seconds needed to complete each project. The third and final line contains $m$ integers $0 \leq s_ i \leq 10\, 000$, the score awarded for each project. You may assume that with enough time investment, it is possible to achieve a perfect score of $10$ every week. The total number of projects will be at most $10^5$.

2 Output

Print the minimum number of seconds needed per week to pass the course. It is guaranteed that the answer is the same for all course grades in $[4.75 - 10^{-6}, 4.75 + 10^{-6}]$

Score

3 2
10 3
5 5 5
5 5 5
4 2
20 20
2 2
8 2
8 8
4 4

8