题目描述

有 $n$ 个木材供应商，每个供应商拥有若干根长度相同的木头。长木头可以锯短，但短木头不能接长。现在有客人需要 $m$ 根长度相同的木头，请计算能满足要求的最大木头长度。

第一个供应商的木头长度和数量直接给出；其他供应商的数据由公式生成。

输入格式

输入一行四个整数 $n,m,l_1,s_1$，分别表示供应商数量、客人需要的木头根数、第一个供应商每根木头长度、第一个供应商木头数量。

对于 $i \ge 2$，第 $i$ 个供应商的木头长度 $l_i$ 和数量 $s_i$ 按如下公式生成：

l_i=((l_{i-1} imes 37011+10193)mod 10000)+1

s_i=((s_{i-1} imes 73011+24793)mod 100)+1

输出格式

输出一行一个整数，表示满足要求的 $m$ 根等长木头的最大长度。

10 10000 8 20

201

数据范围与提示

• $1 \le n \le 10000$
• $1 \le m \le 1000000$
• $1 \le l_1 \le 10000$
• $1 \le s_1 \le 100$
• 可以对答案长度进行二分，并统计每个长度下最多能锯出的根数。

来源

省赛 数组问题 二维数组 结构体