問題一覧 > 通常問題

No.3665 Two Important Tasks

レベル : / AI推定難易度 : 2350 / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 8
作問者 : dyktr_06 / テスター : tyawanmusi t5ugu sepa38
お気に入りにしたユーザー ProblemId : 13883 / 自分の提出
問題文最終更新日: 2026-08-30 03:40:04
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
MMA Contest 022 (順位表) の他の問題:

Problem Statement

There are $N$ jobs, and you are going to choose some of them to do.

If you do the $i$-th job, you must work on it every day during the period from day $L_i$ to day $R_i$. Also, doing the $i$-th job gives you a reward of $C_i$.

Note that you cannot do multiple jobs on the same day.

Now, you know that there are two important jobs that you must do.

You are given $Q$ queries, so answer the following problem for each of them. The $j$-th query is as follows.

  • Output the maximum total reward you can obtain when the important jobs are the $a_j$-th and $b_j$-th jobs. If it is impossible to do both important jobs, output -1.

Constraints

  • $2 \leq N,Q \leq 2 \times 10^5$
  • $1 \leq L_i \leq R_i \leq N$
  • For any integer $p$, there are at most $5$ integers $i$ satisfying $L_i \leq p \leq R_i$
  • $1 \leq C_i \leq 10^9$
  • $1 \leq a_j < b_j \leq N$
  • All input values are integers

Input

The input is given from standard input in the following format.

$N$ $Q$
$L_1$ $R_1$ $C_1$
$L_2$ $R_2$ $C_2$
$\vdots$
$L_N$ $R_N$ $C_N$
$a_1$ $b_1$
$a_2$ $b_2$
$\vdots$
$a_Q$ $b_Q$

Output

Output $Q$ lines.

On the $i$-th line, output the answer to the $i$-th query.

Sample

Sample 1
Input
5 4
1 2 4
3 4 5
2 3 10
5 5 2
1 1 3
1 2
1 3
2 5
3 4
Output
11
-1
10
15

In the $1$-st query, doing the $1$-st, $2$-nd, and $4$-th jobs gives a total reward of $11$.

In the $2$-nd query, the periods of the two important jobs overlap, so you cannot do both.

Sample 2
Input
4 3
1 4 100
1 1 10
2 2 20
3 4 30
1 2
2 4
3 4
Output
-1
60
60

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。