题目描述
Farmer John 的农场迎来了有记录以来最热的夏天，他需要想办法让奶牛们凉快下来。于是，他决定投资购置一些空调。
Farmer John 的 头奶牛（）住在一个牛棚里，牛棚中有一排编号为 的隔间。奶牛 占据其中一段隔间，从第 个隔间开始，到第 个隔间结束。不同奶牛占据的隔间区间互不相交。奶牛们的降温需求各不相同：奶牛 需要被降低 个单位的温度，也就是说，奶牛 占据的每个隔间的温度都必须至少降低 个单位。
牛棚里有 台空调，编号为 （）。第 台空调运行需要花费 单位的钱（），它冷却的隔间范围从第 个隔间到第 个隔间；运行时，第 台空调会使该范围内所有隔间的温度降低 个单位（）。各台空调覆盖的隔间范围可能会相互重叠。
经营农场并非易事，所以 FJ 的预算很紧张。请计算他最少需要花多少钱，才能让所有奶牛都保持舒适。保证如果 FJ 把所有空调全部开启，所有奶牛都会舒适。
输入格式
输入第一行包含 和 。
接下来 行描述奶牛，第 行包含 、 和 。
接下来 行描述空调，第 行包含 、、 和 。
对于除样例之外的所有测试数据，你可以假设 。
输出格式
输出一个整数，表示 FJ 为开启足够的空调、使所有奶牛满足上述条件所需花费的最少金额。
样例
输入
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
提示说明
【样例解释】
一种花费最少的方案是选择冷却区间 、 和 的空调，花费为 。