题目描述

中秋节到了，面条老师准备了 $n$ 个月饼，由于面条老师的手艺惊人，这些月饼并不是圆形的，而是椭圆。所以面条老师需要用长方形的盒子来装这些月饼而不是正方形，其中第 $i$ 个月饼需要的长度为 $a_i$，宽度为 $b_i$。礼品店恰好提供了 $n$ 种盒子，第 $i$ 种盒子的长度为 $c_i$，宽度为 $d_i$。当且仅当某一个盒子的长度大于等于小兔月饼需要的长度，并且宽度大于等于小兔月饼需要的宽度，这个盒子才可以将小兔月饼包装起来。（长和宽无法交换）

一个盒子仅可用于包装一个小兔月饼（如果盒子的长宽有多出来的部分，则舍弃。注意：每一个盒子都可以包装任何一个月饼，而不是第 $i$ 个盒子必须包装第 $i$ 个月饼）虽说礼品店的盒子数量和小兔月饼的数量都是 $n$，但尺寸却不是完全符合。如果盒子大了倒是没事，而盒子小了的话则完全装不下小兔月饼。这可难坏了礼品店的老板——他生怕自己这些尺寸不一的盒子卖不出去。

不过这难不倒面条老师，他找来了放大镜——我们通过放大镜来看这些盒子，那么它的长和宽就都会被放大，这样不就能装得下小兔月饼了吗！

假设我们有一个 $k$ 倍的放大镜，那么第 $i$ 个盒子的长度就会变为 $c_i * k$，宽度会变为 $d_i * k$。

现在面条老师想知道，如果他要用这 $n$ 个盒子包装 $n$ 个小兔月饼，$k$ 的最小值是多少。

输入格式

第一行输入一个正整数 $n$

接下来有 $n$ 行，每行包含四个正整数，分别表示 $a_i, b_i, c_i, d_i$

输出格式

输出一个正整数，表示最小的 k

2
1 1 1 2 
2 4 1 1

2

样例说明

k = 2 时，两个盒子的长宽分别为 2*4, 2*2，用第一张盒子包装第二个小兔月饼，用第二个盒子包装第一个小兔月饼，这样两个盒子都满足“长宽均大于等于对应月饼”，此时所有月饼都被包装。

数据规模与约定

对于 10% 的数据，满足 $n \leq 10, 1 \leq a,b,c,d \leq 100$

对于 30% 的数据，满足 $n \leq 1000, 1\leq a,b,c,d \leq 1000$

对于 50% 的数据，满足 $n \leq 1000, 1 \leq a,b,c,d \leq 100000$

对于 100% 的数据，满足 $1 \leq n \leq 50000, 1 \leq a,b,c,d \leq 100000$

大样例

大样例下载