题目背景

成体系的结论会产出“低猜想水平”的机械推导，但更多的题目中需要“高猜想水平”的灵感。

——command_block 《考前小贴士》

无脑选手出思维题。

题目描述

你要帮 djy 造一棵树，满足以下条件：

• 由 $n$ 个点组成。

• $i$ 号点的度数为 $a_i$。

定义一条边 $(i,j)$ 的价值为 $b_i\times b_j$，你要在满足上述两个条件下，使所有边的价值和最大。

保证存在这样的树。

输入格式

第一行一个整数 $type$，表示数据生成方式。

若 $type=0$：

第二行一个整数 $n$。

第三行 $n$ 个整数，第 $i$ 个数表示 $a_i$。

第四行 $n$ 个整数，第 $i$ 个数表示 $b_i$。

若 $type=1$：

给出一个数据生成器模板：

int a[10000005],b[10000005];
unsigned seed;
unsigned rnd(unsigned x){
	x^=x<<13;
	x^=x>>17;
	x^=x<<5;
	return x;
}
int rad(int x,int y){
	seed=rnd(seed);
	return seed%(y-x+1)+x;
}
void init_data(){
	cin>>seed;
	for(int i=1;i<=n;i++)
		a[i]=1,b[i]=rad(1,500000);
	for(int i=1;i<=n-2;i++)
		a[rad(1,n)]++;
}

第二行一个整数 $n$。

之后调用 init_data()。

第三行一个整数 $seed$。

输出格式

一行一个整数 $ans$，表示最大的价值和。

0
5
1 2 3 1 1 
5 3 1 7 9

42

1
10
114514

249899101316

提示

本题采用捆绑测试。

• Subtask0 (10 pts)：$n\le 6$，$type=0$；
• Subtask1 (20 pts)：$n\le 10^3$，$type=0$；
• Subtask2 (10 pts)：$n\le5\times10^5$，$b_i\le2$，$type=0$；
• Subtask3 (20 pts)：$n\le10^5$，$type=0$；
• Subtask4 (20 pts)：$n\le5\times10^5$，$type=0$；
• Subtask5 (20 pts)：$type=1$。

对于 $100\%$ 的数据，$2\le n\le10^7$，$1\le a_i\le n$，$1\le b_i\le5\times10^5$，$type\in\{0,1\}$，$0\le seed<2^{31}$。