题目描述

​ 封城咯。大爷大妈大叔大姨们抓紧时间抢购咯。

​ 超市里一共有$n$种商品，第$i$种商品的储量是$a_i$，需求量是$b_i$。

​ 然而需求未必都能满足，比如，牙刷的储量是2，需求量是3，饼干的储量是3，需求量是2，这样，牙刷就不够用。

​ 于是，膜法师开始对超市的购物者们施法了，每使用1点法力，就可以使1件第$i(2\leq i)$种商品，变成第$i-1$种商品。

​ 比如在上面的例子中，牙刷编号是1，饼干编号是2，膜法师可以花费1的法力，把1个饼干变成牙刷，这样问题就解决了。

​ 现在，请帮助膜法师算一下，他最少需要花多少的法力，可以使得所有需求都被满足？

输入格式

第一行输入两个整数$n,randseed$，表示商品种类数，数据生成种子。

​ 数组$a,b$将由如下代码生成：

int a[maxn],b[maxn];
int randseed;
unsigned int rnd()
{
  unsigned int r;
  r = randseed = randseed * 1103515245 + 12345;
  return (r << 16) | ((r >> 16) & 0xFFFF);
}
int main()
{
	cin>>n>>randseed;
	int sum=0;
	for (int i=n;i>=1;i--)
	{
		a[i]=rnd()%1000,b[i]=rnd()%1000;
		if (sum+(a[i]-b[i])<0) swap(a[i],b[i]);
		sum+=(a[i]-b[i]);
	}
}

输出格式

一个整数，表示答案，数据保证有解。

样例输入

10 998244353
___________两组样例之间的分割线________________
100 114514

样例输出

700
___________两组样例之间的分割线________________
106509

数据规模与约定

对于$60\%$的数据：$n\leq 1000$。

对于$90\%$的数据：$n\leq 10^5$。

对于$100\%$的数据：$n\leq 10^7$