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.

Do not try for It!

有一个有 $N$ 个点的无向图，第 $i$ 个点的编号是 $i-1$，每个点都有一个点权 $w_i$，一开始所有点互不相连。

有 $N-1$ 次操作，第 $i$ 次操作如下。

• 操作 $1$：形如 1 x，使 $x$ 节点跟 $i$ 连边。
• 操作 $2$：形如 2 x，与 $x$ 节点相邻的节点（不包括 $x$）跟 $i$ 连边。
• 操作 $3$：形如 3 x，与 $x$ 节点相邻的节点（包括 $x$）跟 $i$ 连边。
• 相邻的定义为：如果两个点之间有一条连接两点的边，那么称这两个点是相邻的。
• 保证 $x<i$。

最后，你要选择若干个点，保证他们不能相邻，求出他们的 $w_i$ 之和，使其最大化。

输入格式

对于每组测试数据：

• 第 $1$ 行：$1$ 个整数 $N$；
• 接下来一行输入 $N$ 个正整数 $w_i$。
• 接下来 $N-1$ 行每行 $2$ 个整数 $op,x$，表示 $1$ 次操作，$op$ 代表操作数。

输出格式

一行一个正整数，求出最大化的 $w_i$ 之和.

样例

5
1 2 3 4 5
1 0
1 0
1 0
2 1

14

样例解释

选择点权为 $2,3,4,5$ 的点，和为 $14$。

数据范围

• 对于 $100\%$ 的数据，$op\in[1,3]$，$1\le x\le N\le 10^6,1\le w_i\le 10^9$