#2329. 希蒙的选课方案

希蒙的选课方案

希蒙的选课方案

题目背景

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

题目描述

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

输入格式

第一行共有22个整数n,qn,q

接下来nn行,每行三个整数starti,endi,wistart_i,end_i,w_i,含义见上。

接下来qq行,每行两个整数li,ril_i,r_i,含义见上。

输出格式

你一共需要输出q+1q+1行,第一行为没有时间占用的情况下的答案,接下来qq行,你需要输出当时间占用为线段tit_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<=1001<=n,q<=100

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

对于另外10%的数据,我们保证q=0q=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=153+4+8=15

对于第一个询问的方案为:3,5。和为4+8=124+8=12

对于第二个询问的方案为:4。和为1010