User's AC Ratio

50.0% (2/4)

Submission's AC Ratio

10.5% (2/19)

Description

有一天舜寧在夢中,來到了一個奇怪星球上的一個奇怪小島,化身為奇怪舜寧,
在這個奇怪小島上,大家在大學畢業後都會去一種職前訓練所,叫做研究所;
奇怪舜寧覺得他很厲害,所以並不打算讀研究所就要直接去工作了,
可是他又希望別人覺得他很厲害,因此打算報名推甄並錄取後,再來跟別人炫耀。

奇怪小島今年的推甄規則如下,分為二個階段,第一階段要先繳交一份備審資料,
並選擇要報名的研究所,之後第二階段總共為期 $D$ 天,統一在一個奇怪地點,
每個研究所分別會在第 $b_i$ 到 $e_i$ 天開放面試(包含第 $b_i,e_i$ 天)。

奇怪舜寧報名了總共 $N$ 個研究所,並且全部通過第一階段進入第二階段,
而對於奇怪舜寧來說,上了某一個研究所,可以增加 $c_i$ 的炫耀資本,
但是奇怪舜寧很懶,他只打算選擇一天,並面試 $K$ 所學校後就回家了。

奇怪舜寧雖然很自大,但也的確是很有實力,所以經過第二階段的面試後一定會被錄取。
請問奇怪舜寧選擇其中一天並最多參加 $K$ 所學校的面試,最高能獲得多少炫耀資本?

Input Format

第一行有三個整數 $D, N, K$,
接下來 $N$ 行,每行有三個整數 $c_i,b_i,e_i$,
代表每個學校的面試開放時間與奇怪舜寧可獲得的炫耀資本。

  • $1\le D\le3\times10^5$
  • $1\le N\le3\times10^5$
  • $1\le K\le N$
  • $1\le c_i\le 3\times10^5$, for all $i$
  • $1\le b_i\le e_i\le D$, for all $i$

Output Format

每筆測資輸出一個整數,代表奇怪舜寧能獲得的最高炫耀資本。

Sample Input 1

10 4 2
400 3 5
1500 6 9
800 2 8
200 4 7

Sample Output 1

2300

Sample Input 2

5 3 3
500 5 5
400 1 3
300 2 3

Sample Output 2

700

Hints

Subtasks

No. Testdata Range Score
1 0~9 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1200 65536 65536 1
1 1200 65536 65536 1
2 1200 65536 65536 1
3 1200 65536 65536 1
4 1200 65536 65536 1
5 1200 65536 65536 1
6 1200 65536 65536 1
7 1200 65536 65536 1
8 1200 65536 65536 1
9 1200 65536 65536 1