该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

有$n$个木材供应商（$1 \le n \le 10000$），每个供货商有长度相同、数量一定的木头。长木头可以锯短，但短木头不能接长。有一个客人要求$m$根长度相同的木头，要求计算出供货商提供的木头满足客人要求的最长木头长度。

例如$n=2，m=30$，两个供货商的木头信息为：

• 第1个供货商的木头长度为12，共有10根；
• 第2个供货商的木头长度为5，共有10根。

计算的结果为5，即长度为12的木头一根可锯出两根长度为5的木头（多余部分无用），长度为5的木头保持不动，此时总共可得到30根长度为5的木头，恰好满足客人需求。

输入格式

输入一行整数n, m, l[1], s[1]，各参数的取值范围为：1 ≤ m ≤ 1000000，1 ≤ l[1] ≤ 10000，1 ≤ s[1] ≤ 100。

其中l[1]是第一个供货商木头的长度，s[1]是第一个供货商木头的数量；其余供货商（$i \ge 2$）的木头长度$l[i]$和数量$s[i]$由以下公式递推得到：

输出格式

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

样例输入

10 10000 8 20

样例输出

201