6503: 牛栏空调

农夫约翰的 $�$ 头奶牛 $(1\le �\le 20)$ 住在一个谷仓里，谷仓里有连续的牛栏，编号为 $1-100$ 。 奶牛 $�$ 占据了编号 $[{�}_{�},{�}_{�}]$ 的牛栏。 不同奶牛占据的牛栏范围是互不相交的。 奶牛有不同的冷却要求，奶牛 $�$ 占用的每个牛栏的温度必须至少降低 ${�}_{�}$ 单位。

谷仓包含 $�$ 台空调，标记为 $1-�$ $(1\le �\le 10)$。第 $�$ 台空调需要花费 ${�}_{�}$ 单位的金钱来运行 $(1\le {�}_{�}\le 1000)$ ，如果运行，第 $�$ 台空调将牛栏 $[{�}_{�},{�}_{�}]$ 所有牛栏的温度降低 ${�}_{�}$（$1\le {�}_{�}\le 10^6\text{）}$。 空调覆盖的牛栏范围可能会重叠。

请帮助农夫约翰求出满足所有奶牛需求要花费的最少金钱。

第一行两个整数，分别为 $�$ 和 $�$。

第 $2$ 至 $(�+1)$ 行，每行三个整数，分别为 ${�}_{�}$、${�}_{�}$ 和 ${�}_{�}$ 。

第 $(�+2)$ 至 $(�+�+1)$ 行，每行四个整数， 分别为 ${�}_{�}$、${�}_{�}$、${�}_{�}$ 和 ${�}_{�}$。

2 4
1 5 2
7 9 3
2 9 2 3
1 6 2 8
1 2 4 2
6 9 1 5

10