题目描述

在一个圆形的湖边有 $n$ 座城市排成环形，编号为 $0$ 到 $n-1$。

现在要在一些城市之间修建铁路。铁路可以双向通行，并且每一小段铁路必须连接环上相邻的两个城市。具体来说，对于任意 $i=0,1,\dots ,n-1$，可以在 $i$ 号城市和 $i+1$ 号城市之间修建一条双向通行的铁路，花费为 $C_i$。

城市居民计划在修建铁路之后开通 $P$ 条火车线路，其中第 $i$ 条线路起点和终点分别为 $a_i,b_i$。修建铁路的方案必须保证，对于每一条计划开通的线路，线路起点和终点 $a_i,b_i$ 被铁路（直接或间接）连通。

你需要求出修建铁路花费之和可能的最小值。

输入格式

输入文件名为 cycle.in。

输入文件共四行，每行一个数，依次为 $n,P,M,s$。你需要通过参数 $M,s$ 计算出实际的 $C_i,a_i,b_i$。

具体的计算方式为：

int n, P, M;
long long s;
int a[MAX_P], b[MAX_P], C[MAX_n];

cin>>n>>P>>M>>s;
for (int i=0;i<n;i++) {
	s=(s*1103515245+12345)%(1LL<<31);
	C[i]=1+((s/10)%M);
}
for (int i=1;i<=P;i++) {
	s=(s*1103515245+12345)%(1LL<<31);
	a[i]=((s/10)%n);
	s=(s*1103515245+12345)%(1LL<<31);
	b[i]=((s/10)%n);
}

输出格式

输出文件名为 cycle.out。

输出一行一个非负整数表示答案。

样例

样例输入 1

10
2
1000
474747

样例输出 1

1161

样例解释 1

实际的 $a,b,C$ 值为：

C[]={253, 325, 395, 132, 427, 50, 582, 52, 573, 747} 
a[]={2, 6}
b[]={4, 8}

样例输入 2

3
47
1000
420042

样例输出 2

991

样例输入 3

100
12
1
12345

样例输出 3

83

更多样例

见附加文件。

数据范围

子任务	特殊限制	分值
1	$n, P\le 1000$	$20$
2	$nP\le 3\times 10^6$
3	-	$60$

对于所有数据，$3\le n\le 5\times 10^5, 1\le P\le 10^5, 1\le M \le 1000, 0\le s < 2^{31}$