说明

农夫约翰的 N 头奶牛 (1≤N≤20) 住在一个谷仓里，谷仓里有连续的牛栏，编号为 1−100。奶牛 i 占据了编号  [s i ,t i ] 的牛栏。 (t i≤100)

不同奶牛占据的牛栏范围是互不相交的。 奶牛有不同的冷却要求，奶牛 i 占用的每个牛栏的温度必须至少降低 c i 单位。 

谷仓包含 M 台空调，标记为 1−M(1≤M≤10)。第 i 台空调需要花费  m i 单位的金钱来运行 (1≤m i ≤1000) ，如果运行，第 i 台空调将牛栏 [a i ,b i ] 所有牛栏的温度降低 p i （ 1≤p i ≤10 ^6 ）。

 空调覆盖的牛栏范围可能会重叠。 请帮助农夫约翰求出满足所有奶牛需求要花费的最少金钱。

输入格式

第一行两个整数，分别为 N 和 M。 第 2 至 (N+1) 行，每行三个整数，分别为 s i 、 t i 和 c i 。 

第  (N+2) 至 (M+N+1) 行，每行四个整数， 分别为 a i 、 b i 、 p i 和 m i 。

输出格式

样例

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