1561 - 买木头

题目描述

n 个木材供应商,每个供货商有长度相同一定数量的木头。长木头可以锯短,但短木头不能接长。有一个客人要求 m 根长度相同的木头。要求计算出,此时供货商提供的木头满足客人要求的最长的长度是多少。

例如 n=2,m=30,两个供货商的木头为

12,101 个供货商的木头长度为 12 ,共有 10 根;

5,102 个供货商的木头长度为 5 ,共有 10 根。

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

输入

整数 n,m,L_1,S_11≤n≤10000,1≤m≤1000000,1≤L_1≤10000,1≤S_1≤100

其中 L_1 是第一个供货商木头的长,S_1 是第一个供货商木头数量。其他供货商木头的长度和数量 L_iS_ii≥2),由下面的公式给出:

L_i=((Li-1 \times 37011+10193) \mod 10000)+1

S_i=((Si-1 \times 73011+24793) \mod 100)+1

输出

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

本题测试数据保证一定有解。

样例

输入

10 10000 8 20

输出

201
说明

来源

2015江苏省青少年信息学奥林匹克竞赛复赛

标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 2767
通过人数 1687
金币数量 3 枚
难度 提高


上一题 下一题