题目背景

小 L 打颓被 nodgd 发现，于是他开始做题了。

题目描述

他的 DS 非常菜，于是他把一共 $n$ 道 DS 题加到了自己的计划题单里，其中第 $i$ 道题的有趣程度为 $a_i$。

由于他并不精通 DS，他发现他在做一些题目之前需要先做另一些题目。这样的关系共有 $n - 1$ 组，他还发现每道题都出现在了这些关系中且没有重复。

他发现 $\forall 2 \leq i \leq n$，第 $i$ 题和第 $fa_i$ 题间存在上文所述的关系，且 $1 \leq fa_i < i$。他必须先做第 $fa_i$ 题后才能做第 $i$ 题。

他发现，如果他在做一道题之前高兴程度为 $k$，则他做完第 $i$ 题后，他的高兴程度便会变为 $\min(k, a_i)$。他做题前的高兴程度为无穷大。

他想问你在必须先做第 $1$ 题且不能重复做某一道题的情况下，他在做题的全过程中每做完一道题后高兴程度之和的最大值。

输入格式

第一行，两个整数 $n, seed$；

由于输入量较大，我们采用如下方式生成 $a_i, fa_i$。

C++：

typedef unsigned int uint;

inline uint get_next(uint &seed){
	seed ^= seed << 13;
	seed ^= seed >> 17;
	seed ^= seed << 5;
	return seed;
}

int main(){
	// ...
	for (int i = 1; i <= n; i++){
		a[i] = get_next(seed);
	}
	for (int i = 2; i <= n; i++){
		fa[i] = get_next(seed) % (i - 1) + 1;
	}
	// ...
	return 0;
}

使用其他语言的选手请参考「说明/提示」中的「伪代码参考」。

输出格式

一行，一个整数，表示所求的值。

6 114514

14907285111

提示

样例 #1 解释

在该组样例中 $a = [3398922311, 3077554952, 2933028207, 4018360144, 1263042788, 835814542]$，$fa_2 = fa_3 = fa_4 = 1$，$fa_5 = fa_6 = 2$。

最优方案之一：依次做第 $1, 4, 2, 3, 5, 6$ 题，最大值为 $3398922311 + 3398922311 + 3077554952 + 2933028207 + 1263042788 + 835814542 = 14907285111$。

伪代码参考

其中 $\text{left}(x,d)$ 和 $\text{right}(x,d)$ 分别表示将 $x$ 左移或右移 $d$ 位。

数据规模与约定

本题自动开启捆绑测试和 O2 优化。

对于 $100\%$ 的数据，$1 \leq n \leq 10^7$，$0 \leq seed < 2^{32}$。