当前没有测试数据。

题目描述

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

谷仓包含 𝑀台空调，标记为 1−𝑀(1≤𝑀≤10)。第 𝑖台空调需要花费 𝑚𝑖 单位的金钱来运行 (1≤𝑚𝑖≤1000)，如果运行，第 𝑖 台空调将牛栏 [𝑎𝑖,𝑏𝑖] 所有牛栏的温度降低 𝑝𝑖（1≤𝑝𝑖≤106）。 空调覆盖的牛栏范围可能会重叠。

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

输入格式

第一行两个整数，分别为 𝑁 和 𝑀。

第 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

提示

样例解释 1

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

数据范围

对于 100% 的数据，1≤𝑁≤20， 1≤𝑀≤10, 1≤𝑎𝑖,𝑏𝑖,𝑠𝑖,𝑡𝑖≤100，1≤𝑐𝑖,𝑝𝑖≤106， 1≤𝑚𝑖≤1000。