题意描述

有 $n$ 个敌人，敌人有血条 $a_i$ 和爆炸伤害 $b_i$。你每次可以动用技能击杀一名敌人，随后该敌人会爆炸。当一个敌人爆炸时，会对所有活着的敌人造成 $b_i$ 的爆炸伤害，也即令 $a_j\leftarrow a_j-b_i$。若 $a_i$ 变为 $0$ 或负数，则该敌人死亡随后爆炸。问你至少要动用多少次技能。

然而你不知道 $b_i$ 具体是多少，只知道其在一个区间 $[l_i,r_i]$ 内。对于所有的 $\{b_i\}$，求出最少动用技能次数之和。

$1\leq n\leq 10,1\leq l_i\leq r_i\leq 7,1\leq a_i\leq 70$。

或者

$1\leq n\leq 20,1\leq l_i\leq r_i\leq 15,1\leq a_i\leq 300,r_i-l_i\le1$。

对 $M$ 取模，不保证 $M$ 是质数。

输入格式

$n, m, M$

$a_i, l_i, r_i$

输出格式

$ans$

输入样例

20 15 66666666
153 1 1
204 7 7
209 9 9
27 15 15
276 10 10
30 8 8
43 11 11
229 13 13
194 9 9
148 2 2
126 1 1
243 5 5
124 4 4
84 6 6
125 12 12
79 7 7
159 6 6
240 15 15
244 9 9
59 14 14

输出样例

9