#include<bits/stdc++.h>
using namespace std;

// [1] 全局变量：n为供应商数量，m为客户需要的木头总数量
int n,m; 
// [2] 结构体：存储单个供应商的木头信息，l为木头长度，s为木头数量
struct stu{
    long long l,s;
};
// [3] 动态数组：存储所有供应商的木头信息
vector<stu> arr;

int main() {
    // [4] 输入核心参数：供应商数量n、需要的木头数量m
    cin>>n>>m;
    // [5] 初始化数组大小为n+1，保留从下标1开始的使用习惯
    arr.resize(n+1);
    // [6] 输入第一个供应商的木头长度和数量
    cin>>arr[1].l>>arr[1].s;
    
    // [7] 递推生成剩余n-1个供应商的木头信息
    for(int i=2;i<=n;i++){
        // [8] 递推计算当前供应商的木头长度：按题目公式生成，保证长度≥1
        arr[i].l=((arr[i-1].l*37011+10193)%10000)+1;
        // [9] 递推计算当前供应商的木头数量：按题目公式生成，保证数量≥1
        arr[i].s=((arr[i-1].s*73011+24793)%100)+1;
    }
    
    // [10] 计算所有木头的最大长度，作为二分查找的右边界
    int maxL = 0;
    for(int i=1;i<=n;i++) maxL = max(maxL, (int)arr[i].l);
    
    // [11] 二分查找初始化：left为最小可能长度（1），right为最大木头长度，max_len存储最终答案
    int left=1, right=maxL, max_len=0;
    // [12] 二分查找主循环：通过缩小范围定位最大可行长度
    while(left<=right){
        // [13] 计算当前候选长度mid，用left+(right-left)/2避免整数溢出
        int mid=left+(right-left)/2;
        // [14] 累计当前mid长度下可切割的木头总数，用long long防止溢出
        long long sum=0;
        // [15] 遍历所有供应商，计算总贡献量
        for(int i=1;i<=n;i++){
            // [16] 单个供应商的贡献：每根木头可切出的mid长度数量 × 木头总数
            long long a=(arr[i].l)/mid*arr[i].s;
            sum+=a;
            // [17] 提前终止优化：若总数已满足需求，无需继续遍历
            if(sum>=m)  break;
        }
        // [18] 判断当前mid长度是否满足需求
        if(sum>=m){
            // [19] 可行则更新最大长度，并尝试更大的长度
            max_len=mid; 
            left=mid+1;
        }else{
            // [20] 不可行则尝试更小的长度
            right=mid-1;
        }
    }
    // [21] 输出满足条件的最大木头长度
    cout<<max_len;
    return 0;                  
}