501000177 - 循环

在一个圆形的湖边有 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

更多样例

见附加文件。

数据范围

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