题目描述

有 $n$ 名队员和连续的 $m$ 段激流，位置依次为 $p_0,p_1,\dots,p_m$。

第 $j$ 名队员有：

• 体重 $w_j$；
• 徒步通过任意一段激流旁岸路所需时间 $t_j$；
• 每次上下木筏所需时间 $s_j$。

第 $i$ 段激流有临界重量 $c_i$：若木筏上人员总重量超过 $c_i$，木筏会翻覆，通过该段需 $D_i$ 分钟；否则需 $d_i$ 分钟。

通过一段激流前，可以决定哪些人乘筏、哪些人步行。木筏和步行者并行前进，只有所有人以及木筏都到达下一位置后，才能进行上下筏操作。一次人员调整的耗时等于所有改变位置人员的 $s_j$ 之和。

开始时所有人在 $p_0$ 岸上；结束时所有人必须在 $p_m$ 岸上，并且木筏也必须到达终点。每段激流上木筏至少要有一人。

求最短总时间。

输入格式

第一行两个整数 $n,m$，$1\le n\le10$，$1\le m\le1000$。

接下来 $n$ 行，每行 wj tj sj。

接下来 $m$ 行，每行 ci Di di。

所有数均为不超过 10000 的正整数。

输出格式

输出最短总时间。

样例

2 3
50 5 1
70 20 1
30 15 10
60 100 10
70 100 10

51