Description

A software development company needs to develop two software products and deliver them at the same time. To finish this task as soon as possible, each software is divided into $m$ modules to be completed by the company’s technicians. For each technician, the number of days required to complete any module of the same software is the same and known, but the time to complete a module of the other software may be different. At any given moment, each technician can work on at most one module, and each module must be completed independently by exactly one person; collaboration on a single module is not allowed. During the entire development period, after finishing a module, a technician may proceed to any module of either software. Write a program to determine the earliest day on which the company can deliver the software.

Input Format

The first line contains two space-separated integers $n$ and $m$, where $1 \le n \le 100$, $1 \le m \le 100$. Each of the next $n$ lines contains two space-separated integers $d_1$ and $d_2$. Here, $d_1$ is the number of days this technician needs to complete one module of the first software, and $d_2$ is the number of days needed to complete one module of the second software, where $1 \le d_1, d_2 \le 100$.

Output Format

Output a single line containing an integer $d$, indicating the earliest day after which the company can deliver the software.

3 20
1 1
2 4
1 6

18

Hint

Sample Explanation

The fastest plan is for the first technician to complete $18$ modules of the second software, taking $18$ days; the third technician completes $18$ modules of the first software, taking $18$ days; the remaining modules are completed by the second technician, taking $12$ days. Finishing all modules takes $18$ days. If the first technician completes $17$ modules of the second software and the third technician completes $17$ modules of the first software, and the remaining modules are completed by the second technician, it still takes $18$ days. Therefore, it is impossible to finish in fewer than $18$ days.

Translated by ChatGPT 5