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

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

操作1：形如 1 x，使 x 节点跟 i 连边。

操作2：形如 2 x，与 x 节点相邻的节点（不包括x）跟 i 连边。

操作3：形如 3 x，与 x 节点相邻的节点（包括 x）跟 i 连边。

相邻的定义为：如果两个点之间有一条连接两点的边，那么称这两个点相邻的。保证x<i。

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

输入格式

对于每组测试数据：

第 1 行：1 个整数 N；接下来一行输入 N 个正整数 wi。

接下来 N−1 行每行 2 个整数,op,x，表示 1 次操作，op 代表操作数。

输出格式

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

样例

输入数据 1

5

1 2 3 4 5

1 0

1 0

1 0

2 1

输出数据 1

14

样例解释

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

数据范围

Subtask 1≤1≤x≤N≤10^5得分100;

求大佬帮助