P12519 "MSTOI-R1" Hot Boiling Water

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.

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

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 one integer: the earliest day on which Xiao M's total $rks$ can be $\ge m$. If it cannot be achieved, output `-1`.

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: ```cpp 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$. Test point|Special property ---|--- $1\sim3$|$n\le100$ $4$|$m=0$ $5$|$d_i=0$ $6\sim10$|$n\le10^3$ $11\sim15$|$n\le10^4$ $16\sim20$|None Translated by ChatGPT 5