You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

你管理着一个很大的工坊。

Description

在你的工大坊中，共有$n$个工作台，每个工作台上依次标有它们的序号$1,\cdots,n$。在初始时刻（$0$时刻），所有工作台处于空闲状态。

现在，从某个特殊的渠道，你提前知道了在接下来的一段时间内你的工坊将会发生的事件，事件共有两种：

1. 在时刻$T$，一个新的任务到达，这个任务必须在标有序号$p$的工作台上完成，耗时$d$，收益为$v$。在任何时间，同一个工作台上至多只能有一项任务正在进行，如果该工作台此时空闲，那么你可以接受这项任务并占用此工作台。你将在这项任务完成的时刻获得收益$v$，而如果这项任务在中途被中止，你将无法获得任何收益。
2. 在时刻$T$，你的上级要求你将一些工作台合并，即让标有序号$p$的工作台与标有序号$q$的工作台合并为一个大工作台，在这个合并后的大工作台上，同时标有原$p$工作台上的所有序号和原$q$工作台上的所有序号。如果标有序号$p$的工作台与标有序号$q$的工作台在这次操作前已经是同一个工作台了，那么请忽略这个操作，否则，这个操作必须执行。

在合并工作台时，新工作台最多只能保留一项正在进行的任务：如果合并前的两个工作台在合并时刻均有任务未完成，那么你将可以舍弃任意一个工作台上的任务而保留另一个，被舍弃的任务将不会给你带来任何收益。

现在你想要知道，你该如何操作这些工作台，才能够使得最终的总收益最大。

注意： 接受任务、合并工作台、中止任务等所有操作均可以在瞬间完成；如果新任务到达、旧任务结束、上级要求合并工作台等事件在同一时刻到来，你可以任意选择它们执行的先后顺序。

Format

Input

第一行两个正整数$n,m$，分别代表工作台的数量和事件的数量。

接下来$m$行，每行由一个事件种类编号$opt$和若干个描述事件的参数组成：

• 如果$opt=1$，那么接下来有$4$个正整数$T,p,d,v$，分别表示某一任务到来的时刻、要求的工作台标号、任务耗时与任务收益。
• 如果$opt=2$，那么接下来有$3$个正整数$T,p,q$，分别表示某一合并事件到来的时刻、要合并的两个工作台的标号。

Output

输出一行一个整数，代表在最优操作方案下，你的最大收益（即所有已完成的任务收益之和）。

Samples

6 14
2 3 1 2
2 3 3 4
2 3 4 5
2 3 3 5
2 4 1 3
2 4 1 6
2 4 5 6
1 2 1 2 4
1 2 1 1 1
1 2 2 2 4
1 1 3 3 2
1 2 4 2 8
1 2 5 1 5
1 3 6 9 6

24

10 26
1 39 3 34 50
1 12 2 40 9344
2 15 9 2
1 40 9 5 7796
1 14 7 10 3843
2 15 10 10
1 9 5 11 9032
2 30 1 1
2 25 1 1
1 19 7 6 4918
1 25 7 6 5743
2 26 10 10
1 31 3 11 451
1 13 9 17 8266
1 10 3 37 752
2 3 9 10
1 39 4 27 6104
1 29 1 28 64
2 2 3 5
1 8 6 38 5538
2 36 4 9
2 14 10 3
1 37 2 34 1123
2 35 8 2
1 15 6 12 6172
2 30 10 5

33725

Limitation

$1\le p,q\le n\le 10^5$

$1\le m\le 3\times 10^5$

$1\le T,d,v\le 10^9$