逃生之路

还在茫茫宇宙中……

还是这群生物 ccj，因为上次的打击太草率了，同时被他人侦测到了。在得知自己即将受到黑暗森林打击之后，选择逃离自己的家园。 他们的旅程计划在一条线上，其中，我们约定，一号点是他们的家园，有无限多个生物。每一个星球，都可以向之后连续的 $p$ 个星球进行转移。但由于每个星球的”体质“不同，每个星球所能接受的生物数量限定在一个范围 $[b,a]$ 之间。而且，由于星球本身资源匮乏，到达每一个星球都需要消耗星球一定的能源，补充飞船能源。并且又因为宇宙空间的复杂，所以这个能源是关于星球所接受生物数量的一个多项式。飞船年久失修，所以遇到任何星球必定前往去补充能源。 可惜这群生物有一个睿智的头领，他希望最终能有生物到达可以生存的星球，而且消耗的总能源要尽量少。那群生物对这个头领很失望，于是把任务丢给你。 请求出有生物到达可生存星球的情况下，最少的能源消耗是多少？

第一行两个整数$n$和$p$，表示有$n$个星球（包括他们的家园和目的地），每次向后跳$p$个，保证 $p\le n-1$。 接下来有 $2\times n-2$ 行，偶数行有三个数字，$a_i$、$b_i$ 和 $f_i$，$i$ 从 $2$ 开始，表示第 $i$ 个星球能承载的生物数范围和这个星球是否能够生存，$f_i$ 为 $1$ 即能生存，$0$ 即为不能生存。 奇数行先有一个数字 $k$，表示这个多项式是 $k$ 次，接下来 $k+1$ 个整数，表示从高到低每一项的系数 $wi$。

一个整数 $ans$ 表示花费最少的能源是多少，如果没有一个生物能到达，输出**"die"**（不包括引号）。

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

**样例解释** 样例一中从 $1\to 2$ 两个ccj，$2\to 3$ 两个 ccj，$2\times 2\times 30+2\times 17+28+2\times 2\times 47+2\times 56-60=422$ 样例二由于没有任何一个星球可以生存，故 die。 $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$。 保证多项式函数二阶导函数在 $x∈[1,100]$ 时恒大于 $0$。