Background

Xiao M has recently been playing a new game, where $rks$ is a value used to measure a player's strength. $rks$ is divided into single-song $rks$ and total $rks$, and both keep two decimal places.

After playing a song, you will get a score $acc$ (accuracy), shown as a percentage.

Problem Description

Each song has a difficulty constant. A song is counted toward $rks$ only when its $acc\ge 70\%$; otherwise, the song's $rks$ is $0$. The single-song $rks=[\frac{(100\times acc-55)}{45}]^2\times$ difficulty constant.

If you play the same song multiple times, its single-song $rks$ keeps the maximum value among all attempts. Total $rks=$ the average of these $5$ single-song $rks$ values: the largest $4$ single-song $rks$, and the largest single-song $rks$ among songs with $acc$ equal to $100\%$ (if there is no song with $acc$ equal to $100\%$, then this item is treated as $0$).

For convenience of representation and calculation, both single-song $rks$ and total $rks$ should keep $2$ decimal places (no rounding).

Xiao M has $n$ songs to play. For the $i$-th song, the difficulty constant is $c_i$. On day $1$, Xiao M can reach $a_i\%$ accuracy, and on day $k$, Xiao M can reach $min(100\%,a_i\%+(k-1)\times b_i\%)$. Xiao M plays all these $n$ songs every day. Find the earliest day on which Xiao M's total $rks$ can be $\ge m$.

Input Format

The first line contains a positive integer $n$ and a decimal number $m$.

The next $n$ lines each contain three decimal numbers $a_i$, $b_i$, $c_i$.

The next line contains $5$ decimal numbers $d_i$. The first $4$ are Xiao M's largest $4$ single-song $rks$, and the last one is the largest single-song $rks$ among songs with $acc$ equal to $100\%$. Note that the songs corresponding to these $5$ single-song $rks$ values are all different from the above $n$ songs, and you may treat them as Xiao M's results on day $0$.

Output Format

Output one integer: the earliest day on which Xiao M's total $rks$ can be $\ge m$. If it cannot be achieved, output -1.

3 8.31
70.00 10.00 9.50
60.00 40.00 9.00
50.00 10.00 9.10
8.00 0.00 9.00 8.00 9.00

2

3 11.00
70.00 10.00 9.50
100.00 10.00 9.00
50.00 10.00 9.10
15.10 15.10 15.10 15.10 15.10

0

Hint

The testdata guarantees that all input decimals have exactly two decimal places. Note that all decimals during the computation must also keep two decimal places (no rounding) (for example, when computing single-song $rks$, after $\div 45$, you must keep $2$ decimal places before continuing), otherwise your result may differ from the answer.

It is recommended to use the following code to keep two decimal places:

double retain2(double x)
{
	int y;
	double z;
	x*=100;
	y=x;
	z=y/100.0;
	return z;
}

Constraints for $100\%$ of the testdata: $1\le n\le10^5$, $0\le m\le17$, $0\le a_i\le100$, $0.01\le b_i\le100$, $1\le c_i\le17$, $0\le d_i\le17$.

Translated by ChatGPT 5