#215574. [JOI 2026 SemiFinal] 宝石商 / Jeweler

JOI 君は宝石店を経営している．宝石店には宝石を買おうとしている客が 人おり，これらの客には から までの番号が付けられている．客 () は時刻 から時刻 までの間の任意の時刻に店を訪れることができ，宝石を 個購入しようとしている．

JOI 君は忙しいため，常に店を開けておくことができない．そこで，店を開ける時間について 個の案を考えた．案には から までの番号が付けられており，案 () は，時刻 から時刻 までの間店を開けるというものである．それぞれの案について，客 () は，自分が訪れることができる時間帯に店が開いている時刻があれば，店を訪れ宝石を 個購入する．逆にそうでない場合，客 は店を訪れず，宝石を購入しない．ただし，JOI 君の店には十分な数の宝石があり，宝石が売り切れることはないものとする．

JOI 君の店の客の情報と店を開けておく時間の案が与えられたとき，それぞれの案について，宝石が合計でいくつ売れるかを求めるプログラムを作成せよ．

入力は以下の形式で標準入力から与えられる．

標準出力に 行出力せよ． 行目 () には，案 において宝石が合計でいくつ売れるかを出力せよ．

样例输入 1

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

样例输出 1

60
0
50

样例输入 2

4
10 90 1
40 60 2
10 20 4
80 90 8
3
1 15
1 60
1 100

样例输出 2

5
7
15

样例输入 3

10
55 882 861052753
104 734 331227764
492 694 240198464
481 506 377367203
131 185 327968773
124 129 970226535
92 125 133053911
356 442 758055457
21 759 730522637
259 481 948997757
9
50 287
510 735
158 431
113 768
328 894
783 881
163 692
42 862
43 752

样例输出 3

4303050130
2163001618
3957825141
5678671254
4247422035
861052753
4575390808
5678671254
5678671254

Sample Explanation 1

案 1 では，時刻 から時刻 まで店を開ける．客 1 は時刻 に，客 2 は時刻 に，客 3 は時刻 に店で宝石を買うことができ，宝石は合計で 個売れる．

案 2 では，時刻 から時刻 まで店を開ける．どの客も店が開いている時刻に訪れることができないため，宝石は合計で 個売れる．

案 3 では，時刻 から時刻 まで店を開ける．客 2，客 3 ともに時刻 に店で宝石を買うことができ，宝石は合計で 個売れる．

この入力例は小課題 1, 5 の制約を満たす．

Sample Explanation 2

案 1 では，客 1 と客 3 が店で宝石を買うことができ，宝石は合計で 個売れる．

案 2 では，客 1，客 2，客 3 が店で宝石を買うことができ，宝石は合計で 個売れる．

案 3 では，すべての客が店で宝石を買うことができ，宝石は合計で 個売れる．

この入力例は小課題 1, 3, 4, 5 の制約を満たす．

制約

• ．
• ()．
• ()．
• ．
• ()．
• 入力される値はすべて整数である．

小課題

1. 点．
2. 点 ()．
3. 点 ()．
4. 点 ()．
5. 点追加の制約はない．