题目背景

小 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$。

伪代码参考

$$\def{\b}#1{ \textbf{ #1 } }\def{\t}#1{\text{ #1 }}\def{\s}{\quad}\def{\f}#1{\textsf{ #1 }} \def{\l}{\underline{\kern{300pt}}\\[-10pt]} \def{\r}{\overline{\underline{\kern{300pt}}}} \begin{aligned} &\r\\&\b{Algorithm:}\t{Get }a_i,fa_i\\[-13pt]&\l\\ &\begin{aligned} \f{1.}&\b{function} \b{\color{red}unsigned int} \t{getnext}(\b{\color{red}unsigned int}\&seed): \\ \f{2.}&\s seed=seed\oplus\t{left}(seed,13)\\ \f{3.}&\s seed=seed\oplus\t{right}(seed,17)\\ \f{4.}&\s seed=seed\oplus\t{left}(seed,5) \\ \f{5.}&\s \b{return} seed\\ \f{6.}&\b{function} \t{main}(n):\\ \f{7.}&\s \b{for} i \b{from} 1 \b{to} n \b{step}1\\ \f{8.}&\s\s a_i=\t{getnext}(seed)\\ \f{9.}&\s \b{end for} \\ \f{10.}&\s \b{for} i \b{from} 2 \b{to} n \b{step}1\\ \f{11.}&\s\s fa_i=\t{getnext}(seed)\bmod(i-1)+1\\ \f{12.}&\s \b{end for} \\ \end{aligned}\\[-12pt] &\r \end{aligned} $$

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

数据规模与约定

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

$$\newcommand{\arraystretch}{1.5} \begin{array}{c|c|c}\hline\hline \textbf{Subtask} & \bm{n \leq} & \textbf{分值} \\\hline \textsf{1} & 10 & 10 \\\hline \textsf{2} & 10^4 & 20 \\\hline \textsf{3} & 10^6 & 20 \\\hline \textsf{4} & \text{无特殊限制} & 50 \\\hline\hline \end{array} $$

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