Problem Background

Still in the vast universe...

Problem Description

This group of creatures, ccj, faced a hasty attack previously and were detected by others. Upon learning that they are about to be struck by a dark forest attack, they decide to flee their home.

Their journey is planned along a straight line, where the first point is their home, containing an infinite number of creatures. Each planet can transfer creatures to the next $p$ consecutive planets. However, due to the different "constitution" of each planet, the number of creatures a planet can accommodate is limited within a range $[b, a]$. Moreover, due to the scarcity of resources on each planet, reaching a planet consumes a certain amount of energy to replenish the spacecraft's energy. This energy consumption is a polynomial function of the number of creatures received by the planet. The spacecraft is old and must stop at any planet to replenish energy.

Unfortunately, these creatures have a wise leader who hopes that some creatures can reach a habitable planet with the least total energy consumption. The creatures are disappointed with this leader and have assigned the task to you.

Calculate the minimum energy consumption required for any creature to reach a habitable planet.

Input Format

The first line contains two integers $n$ and $p$, indicating there are $n$ planets (including their home and destination), and each jump is $p$ planets ahead, ensuring $p \leq n-1$.

The next $2 \times n - 2$ lines are divided into pairs. Even-numbered lines contain three numbers, $a_i$, $b_i$, and $f_i$, where $i$ starts from 2, representing the capacity range of the $i$-th planet and whether it is habitable, with $f_i$ being 1 if habitable and 0 if not.

Odd-numbered lines start with a number $k$, indicating the polynomial is $k$-th degree, followed by $k+1$ integers representing the coefficients $w_i$ from highest to lowest degree.

Output Format

An integer $ans$ indicating the minimum energy consumption. If no creature can reach a habitable planet, output "die" (without quotes).

Sample Input and Output

Input Sample #1

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

Output Sample #1

422

Input Sample #2

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

Output Sample #2

die

Input Sample #3

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

Output Sample #3

21071866

Notes

Sample Explanation

In Sample 1, two creatures move from $1 \to 2$, and two creatures move from $2 \to 3$. The total energy consumption 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 habitable, the output is "die".

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

The second derivative of the polynomial function is guaranteed to be greater than 0 for $x \in [1, 100]$.

见题面 Input 部分

见题面 Output 部分