3629. [LOJ β Round]ZQC 的拼图

【题目描述】

$ZQC$ 和他的朋友在玩拼图。她们有 $n$ 块神奇的拼图，还有一块拼图板。

拼图板是一个 $m * m$ 的正方形网格，每格边长为 $1$，如图所示。

每块拼图都是直角三角形，正面为白色，反面为黑色，拼图放在拼图板上时，必须正面朝上，直角顶点必须与拼图板上的一个格点重合.

两条直角边分别向左和向下。拼图可以重叠在一起。拼图的左/下部分可以超过拼图板的边界，如图所示。

这些拼图有一个优点，就是能伸缩，当然，拼图伸缩是要按基本法来的，具体说来就是：你可以选择一个正整数 $k$，并使所有拼图的每条边长都变成原来的 $k$ 倍。

朋友摆好拼图后，$ZQC$ 需要控制一个玩具小人儿从拼图板的左下角跑到右上角，玩家小人儿路线上的任何一点（包括端点）都要在某块拼图板上（边界或顶点也可以），现在 $ZQC$ 想知道他的朋友最少要把拼图的边长扩大到原来的几倍才存在一种摆放方式使得他能找到这样一条路线。

为了区分不同的拼图板，图中给他们染了不同的颜色。右图中紫色的线表示小人的一条路线。

【输入格式】

第一行两个正整数 $n$ 和 $m$ ,表示有 $n$ 块拼图，拼图板边长为 $m$。

接下来 $n$ 行，每行包含两个正整数 $a_i,b_i$, 表示第 $i$ 块拼图初始时的水平直角边长为 $\frac{1}{a_i}$，垂直直角边长为 $\frac{1}{b_i}$。

【输出格式】

输出一行一个整数 $k$ 表示拼图的边长最少要扩大到原来的 $k$ 倍。

【样例输入1】

3 20
1 1
2 4
1 6

【样例输出1】

18

【样例1说明】

设 $(x,y)$ 表示拼图板从左下角向右 $x$ 格，向上 $y$ 格的位置，一种方案是三块拼图板的右上角分别在 $(20,20),(20,2),(18,0)$，另一种方案是三块拼图板右上角分别在 $(0,17),(3,20),(20,20)$。

【样例输入输出2】

输入输出样例2

【数据规模与约定】

对于 $30\%$ 的数据，所有拼图的$ a_i $和$ b_i $均相等;

对于 $100\%$ 的数据，$ 1\le n \le 100, 1 \le m \le 100, 1 \le a_i,b_i \le 10^6 $;

【来源】

LOJ#500,「LibreOJ β Round」Task 1

Skylake