题目描述: 有n个木材供应商（1<=n<=2000000）,每个供货商有长度相同一定数量的木头。长木头可以锯短,但短木头不能接长。有一个客人要求m根长度相同的木头。要求计算出,此时供货商提供的木头满足客人要求的做场的长度是多少。

例如n=2,m=30,两个供货商的木头为 12,10第1个供货商的木头长度为12,共有10根； 5,10第2个供货商的木头长度为5,共有10根。

计算的结果为5,即长度为12的木头一根可锯出两根长度为5的木头,多余的无用,长度为5的木头不动,此事可得到30根长度为5的木头。

输入 输入:整数n,m,l1,s1（1<=m<=100000000,1<=l1<=10000,1<=s1<=100）

其中l1是第一个供货商木头的长,s1是第一个供货商木头数量。其他供货商木头的长度和数量li和si（i>=2）,由下面的公示给出： li=((li-1×37011+10193) mod 10000)+1 si=((si-1×73011+24793) mod 100)+1

输出 输出 :一个整数,即满足要求的m根长度相同的木头的最大长度。

样例输入: 10 10000 8 20

样例输出 201