6503: 牛栏空调

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

农夫约翰的  头奶牛 (120) 住在一个谷仓里,谷仓里有连续的牛栏,编号为 1100 。 奶牛  占据了编号 [,] 的牛栏。 不同奶牛占据的牛栏范围是互不相交的。 奶牛有不同的冷却要求,奶牛  占用的每个牛栏的温度必须至少降低  单位。

谷仓包含  台空调,标记为 1 (110)。第  台空调需要花费  单位的金钱来运行 (11000) ,如果运行,第  台空调将牛栏 [,] 所有牛栏的温度降低 1106。 空调覆盖的牛栏范围可能会重叠。

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

Input

第一行两个整数,分别为  和 

第 2 至 (+1) 行,每行三个整数,分别为  和  。

第 (+2) 至 (++1) 行,每行四个整数, 分别为  和 


Output

一个整数,表示最少花费的金钱。

Sample Input Copy

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

Sample Output Copy

10

HINT

样例解释 

一种花费最少的可能解决方案是选择那些冷却区间为 [2,9] 、[1,2] 和 [6,9] 的空调,成本为 3+2+5=10 。

数据范围

对于 100% 的数据,120, 1101,,,1001,106, 11000

来源:USACO23JAN