希蒙的选课方案

题目背景

小赛码近期开设了许多有趣的课程，总共有$n$个，每完成一个课程都可以得到一个积分$w_i$，而每个课程开设的时间段是固定的，可以描述成从$start_i$时间到$end_i$时间。请注意，希蒙是一个专一的人，他在一个时间只会上一节课。但希蒙有一个时间段无法正常上课，所以希蒙想知道，他该如何选择课程，以获得更多的积分呢？

题目描述

给定一条时间轴与$n$条带权线段，你一共需要处理$q$个询问，每个询问会给出一个段点为$l_i,r_i$的线段$t_i$，你需要选择一些线段，使得这些线段互不相交，且与线段$t_i$不相交，使得这些线段的权值和最大，你只需要输出这个最大的权值和即可。

输入格式

第一行共有$2$个整数$n,q$。

接下来$n$行，每行三个整数$start_i,end_i,w_i$，含义见上。

接下来$q$行，每行两个整数$l_i,r_i$，含义见上。

输出格式

你一共需要输出$q+1$行，第一行为没有时间占用的情况下的答案，接下来$q$行，你需要输出当时间占用为线段$t_i$的情况下的答案。

样例 #1

样例输入 #1

5 2
1 4 5
1 2 3
3 4 4
1 5 10
5 6 8
1 2
6 6

样例输出 #1

15
12
10

提示

数据范围：

对于10%的数据，我们保证$1<=n,q<=100$。

对于30%的数据，我们保证$1<=n,q<=1000$。

对于另外10%的数据，我们保证$q=0$。

对于100%的数据，我们保证$1<=start_i,end_i,l_i,r_i,n,q<=2\cdot10^5,1<=w_i<=10^9$。

样例解释：

没有时间占用时的方案为：2，3，5。和为$3+4+8=15$。

对于第一个询问的方案为：3，5。和为$4+8=12$。

对于第二个询问的方案为：4。和为$10$。