Description

XX 传说是一款经典的卡牌游戏，游戏由两名玩家以回合制的形式进行。每名玩家在场上拥有若干名随从且拥有的随从数上限为 $l$ (保证初始随从数量不会超出上限)。现将场上随从分为三类。

• 类型 $1$：拥有若干血量，无其余效果。
• 类型 $2$：拥有若干血量 , 当存在于场上未死亡时能为其所在一方增加 $1$ 点额外魔法伤害（持有该随从的一方使用的法术牌增加 $1$ 点伤害，详情见样例说明）。
• 类型 $3$：拥有若干血量，拥有一个 $\textbf{亡语}$（死亡时可以触发一些特定效果）$,$ 当自身死亡时可以召唤两个类型 $1$ 随从，且其中一个随从拥有 $x$ 点血量，另一个拥有 $x - 2$ 点血量，若亡语召唤出来的随从血量 $\leq 0$ 则直接死亡，同时优先召唤血量高的随从，若超出随从数量上限则什么也不会发生 (详情见样例说明)。

亵渎是 XX 传说中术士的一张 $\textbf{法术}$ 牌。其效果是对全场随从造成 $1$ 点伤害，若有随从死亡则重复对全场随从造成 $1$ 点伤害，直到没有随从死亡为止。对随从造成的伤害是根据随从出现在场上的顺序依次结算的。当一名随从触发亡语时，后续的随从可能即将受到此次伤害而死亡，但由于还没有轮到结算，依旧视为在场上且占据随从上限。

现在是你的回合，你想知道现在直接打出一张亵渎直到亵渎结束后一共能击杀多少随从(包括己方随从)。

Format

Input

第一行给出两个整数 $l, n\ (1 \leq l, n \leq 10^6)$ 表示随从上限以及现在场上拥有的随从数量，题目保证现在场上已存在的双方随从数量分别不会超过随从上限。

接下来 $n$ 行，每行有三或四个数，表示现在该随从的状态。每行第一个数 $P_i\ (0\leq P_i \leq 1)$ 表示随从归属，若 $P_i$ 为 $1$ 则为己方随从，反之为对方随从，第二个数 $s_i(1\leq s_i \leq 3)$ 表示随从种类，第三个数 $a_i\ (1 \leq a_i \leq 10^6)$ 表示随从血量，若该随从为类型 $3$ 则该行还将给出第四个数 $x_i\ (1\leq x_i \leq 10^6)$ 表示召唤出较高随从的血量值。

Output

输出一个整数，表示通过这张亵渎击杀的随从数。

Samples

5 5
1 3 5 3
1 1 1
1 3 5 7
1 2 4
1 3 5 4

6

1000 2
0 2 100
1 3 1 2

1

Note

对于第一个样例。

释放亵渎后，第一次造成伤害时，由于场上存在 $1$ 个类型 $2$ 己方随从，因此造成 $2$ 点伤害。全场随从剩余血量按出现顺序依次为 $[3, -1, 3, 2, 3]$，有一名随从死亡，因此可以再造成一次伤害。此时场上剩余随从 $4$ 名，按出现顺序状态分别为 $[[1\ 3\ 3\ 3], [1\ 3\ 3\ 7], [1\ 2\ 2], [1\ 3\ 3\ 4]]$，累计通过亵渎杀死随从 $1$名。

第二次造成伤害时，由于场上存在 $1$ 个类型 $2$ 己方随从，因此造成 $2$ 点伤害。全场随从剩余血量按出现顺序（此次伤害前已死亡不记）依次为 $[1, 1, 0, 1]$，有一名随从死亡，因此可以再造成一次伤害。此时场上剩余随从 $3$ 名，按出现顺序状态分别为 $[[1\ 3\ 1\ 3], [1\ 3\ 1\ 7], [1\ 3\ 1\ 4]]$，累计通过亵渎杀死随从 $2$ 名。

第三次造成伤害时，由于场上不存在类型 $2$ 己方随从，因此造成 $1$ 点伤害。全场随从剩余血量按出现顺序（此次伤害前已死亡不记）依次为 $[-1, -1, -1]$，有三名随从死亡，依次结算死亡顺序和亡语。第一名随从死亡时，依次召唤 $2$ 名随从 $[1\ 1\ 3]$ 和 $[1\ 1\ 1]$，此时场上有 $4$ 名随从（因为还未结算后两名随从的死亡）。第二名随从死亡时，依次召唤 $2$ 名随从 $[1\ 1\ 7]$ 和 $[1\ 1\ 5]$，此时场上有 $5$ 名随从。第三名随从死亡时，因为亡语效果希望召唤 $2$ 名随从 $[1\ 1\ 4]$ 和 $[1\ 1\ 2]$，但是在召唤前者后随从数量为 $5$ 达到上限，无法再召唤第二名。此时场上剩余随从 $5$ 名，按出现顺序状态分别为 $[[1\ 1\ 3], [1\ 1\ 1], [1\ 1\ 7], [1\ 1\ 5], [1\ 1\ 4]]$，累计通过亵渎杀死随从 $5$ 名。

第四次造成伤害时，由于场上不存在类型 $2$ 己方随从，因此造成 $1$ 点伤害。全场随从剩余血量按出现顺序（此次伤害前已死亡不记）依次为 $[2, 0, 6, 4, 3]$，有一名随从死亡，累计通过亵渎杀死随从 $6$ 名。

第五次造成伤害时，没有随从死亡，亵渎合计杀死随从 $6$名。

对于第二个样例。

第一次造成 $1$ 点伤害，第二名随从死亡，召唤 $2$ 名随从 $[1\ 1\ 2]$ 和 $[1\ 1\ 0]$，其中后者血量 $\leq 0$ 直接死亡。但这个死亡并不是因为亵渎的伤害而死亡，因此不统计。

第二次造成 $1$ 点伤害，没有随从死亡，累计杀死随从 $1$ 名。

Limitation

1s, 1024KiB for each test case.