题目描述
有 n 个木材供应商,每个供应商有长度相同的一定数量的木头。长木头可以锯短,但短木头不能接长。有一个客人要求 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。其中 l1 是第一个供货商木头的长度,s1 是第一个供货商木头的数量。其他供货商木头
的长度和数量 li 和 si(i≥2)由下面的公式给出:
- li=((li−1×37011+10193)mod10000)+1;
- si=((si−1×73011+24793)mod100)+1。
输出格式
一个整数,即满足要求的 m 根长度相同的木头的最大长度。
提示
1≤n≤104,1≤m≤106,1≤l1≤104,1≤s1≤100。