← 返回题目列表

Codeforces · 1455/G

G. 禁止值

中文机器翻译题面 查看原题

Polycarp 正在编辑一个复杂的计算机程序。首先,声明变量 $$$x$$$ 并将其分配给 $$$0$$$。然后有两种类型的指令:

1. 设置 $$$y$$$ $$$v$$$ — 为 $$$x$$$ 分配一个值 $$$y$$$ 或花费 $$$v$$$ burles 删除该指令(因此,不重新分配 $$$x$$$);
2. if $$$y$$$ $$$\dots$$$ end 块 — 如果 $$$x$$$ 的值为 $$$x$$$ 则执行 if 块内的指令,否则忽略该块。

if 块内部可以包含 set 指令和其他 if 块。

然而,当 $$$x$$$ 的值被分配给 $$$s$$$ 时,计算机崩溃并立即着火。波利卡普希望防止这种情况发生,并尽可能减少开支。

他可以花费最少的 burles 来删除设置指令以从不将 $$$x$$$ 分配给 $$$s$$$?

输入

第一行包含两个整数 $$$n$$$ 和 $$$s$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le s \le 2 \cdot 10^5$$$) — 程序中的行数和 $$$x$$$ 的禁止值。

以下 $$$n$$$ 行描述了该程序。每条线都是以下三种类型之一:

1. 设置 $$$y$$$ $$$v$$$ $$$(0 \le y \le 2 \cdot 10^5, 1 \le v \le 10^9)$$$;
2. 如果 $$$y$$$ $$$(0 \le y \le 2 \cdot 10^5)$$$;
3.结束。

每个 if 指令都与一个 end 指令相匹配。每个结束指令都有一个 if 指令来匹配。

输出

打印一个整数——Polycarp 可以花费在删除设置指令以永远不会将 $$$x$$$ 分配给 $$$s$$$ 上的最小 burles 数量。

示例

输入 #1

5 1
set 1 10
set 2 15
if 2
set 1 7
end

输出 #1

17

输入 #2

7 2
set 3 4
if 3
set 10 4
set 2 7
set 10 1
end
set 4 2

输出 #2

4

输入 #3

9 200
if 0
set 5 5
if 5
set 100 13
end
if 100
set 200 1
end
end

输出 #3

1

输入#4

1 10
set 1 15

输出#4

0