Background

Still in the vast universe...

Problem Description

It is still this group of creatures, ccj. Because the last strike was too hasty, they were detected by others. After learning that they are about to be hit by the Dark Forest strike, they choose to leave their homeland.

Their trip is planned along a straight line. We define planet $1$ as their homeland, which has infinitely many creatures. From each planet, they can move to the next consecutive $p$ planets. However, due to different “constitutions” of planets, each planet can accept only a number of creatures within the range $[b,a]$. Also, because each planet itself lacks resources, arriving at each planet requires consuming a certain amount of the planet’s energy to replenish the ship’s energy. Because space is complex, this energy cost is a polynomial in the number of creatures accepted by the planet. The ship is old and poorly maintained, so whenever they encounter any planet, they must go to it to replenish energy.

Unfortunately, these creatures have a “wise” leader. He hopes that in the end, there will be creatures that reach a planet where they can survive, and the total energy consumed should be as small as possible. The creatures are very disappointed with this leader, so they throw the task to you.

Please compute: under the condition that some creatures can reach a survivable planet, what is the minimum total energy consumption?

Input Format

The first line contains two integers $n$ and $p$, meaning there are $n$ planets (including their homeland and the destination). Each move can jump forward up to $p$ planets, and it is guaranteed that $p\le n-1$.

Next there are $2\times n-2$ lines.

On even-numbered lines, there are three numbers $a_i$, $b_i$, and $f_i$, with $i$ starting from $2$, meaning the acceptable range of creature counts on planet $i$ and whether this planet is survivable. If $f_i=1$, it is survivable; if $f_i=0$, it is not.

On odd-numbered lines, there is first a number $k$, meaning this polynomial is of degree $k$. Then there are $k+1$ integers, giving the coefficients $wi$ of each term from highest degree to lowest degree.

Output Format

Output one integer $ans$, the minimum energy cost. If no creature can reach any survivable planet, output "die" (without quotes).

3 1
5 2 0
2 30 17 28
5 1 1
2 47 56 -60

422

3 1
1 1 0
1 1 1
1 1 0
1 1 1

die

10 3
23 16 1
3 25 15 -27 47
43 38 0
3 19 35 40 -11
43 37 0
3 70 22 8 -28
41 36 0
3 86 -8 21 -59
39 33 1
3 83 37 -26 56
18 12 0
3 3 96 -75 43
50 43 0
3 85 -2 47 -36
48 41 1
3 36 -4 83 -61
14 8 1
3 33 13 35 -24

21071866

Hint

Sample explanation

In sample 1, move $1\to 2$ with $2$ ccj, and $2\to 3$ with $2$ ccj. The cost is $2\times 2\times 30+2\times 17+28+2\times 2\times 47+2\times 56-60=422$.

In sample 2, since no planet is survivable, output die.

Constraints: $2\le n\le 100\quad |w|\le 100\quad 1\le b\le a\le 100\quad 1\le k\le 5\quad 0\le p\le 10$。

It is guaranteed that the second derivative of the polynomial function is always greater than $0$ when $x∈[1,100]$.

Translated by ChatGPT 5