清凉猪舍

题目描述

在小猪佩奇的家中，夏天格外炎热，猪妈妈希望为她的孩子们提供更加凉爽的环境。于是，她决定在家中安装空调。

小猪佩奇的家里住着 N 头猪（1≤N≤20），他们居住在一个由一排编号为1…100 的猪栏中。第 i 头猪占用一定范围的猪栏，起始编号为 si​ ，结束编号为ti​。​不同猪占用的猪栏范围互不重叠​​。

每头猪需要的冷却量不同。第 i 头猪需要的冷却量为ci​，也就是​它占用的所有猪栏都需要降温至少 ci​个单位​。

猪栏中安装了 M 个空调，编号为 1…M（1≤M≤10）。第 i 个空调需要花费 mi​ 个单位的费用（1≤mi​≤10^3），并且它会对编号为 ai​ 到 bi​ 的猪栏进行降温，每个猪栏的降温量为 pi​ 个单位（1≤pi​≤10^6）。空调所覆盖的猪栏范围​可能会重叠​​。

家庭的经营并不容易，所以猪妈妈需要在紧张的预算内解决这个问题。请确定她需要花费的最少费用，以确保所有的猪都能感到舒适。

保证如果所有空调都运行，所有猪都能感到舒适。

输入格式

第一行输入 N 和 M 。

接下来的 N 行描述每头猪，第 i 行包含 si​，ti​ 和 ci​ 。

接下来的 M 行描述每个空调，第i行包含 ai​，bi​， pi​ 和 mi​。

输出格式

输出一个整数，表示猪妈妈需要花费的最少费用。

样例输入 #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

样例输出 #1

10

提示

数据范围

对于 100% 的数据，1≤N≤20，1≤M≤10,1≤ai​,bi​,si​,ti​≤100, 1≤ci​,pi​≤10^6， 1≤mi​≤1000。