说明

一家物流公司使用 $n$ 种不同型号的机器人在仓库中工作。机器人可以在任意时刻开始充电，不需要等到电量完全耗尽。同样，充电可以在任意时刻结束，不必等到电池充满。唯一的要求是保证每个机器人在任意连续 $t_i$ 分钟内能够获得总计 $c_i$ 分钟的充电时间。

公司计划在仓库中设置 $k$ 个充电站，充电站可以为任何一种型号的机器人充电，每个充电站在任意时刻只能为一个机器人充电。机器人除了在充电时间外，其余时间都处于运行状态。为了保证运行效率，公司希望安排机器人的充电时间表，将每个机器人分别分配到一个充电站上（分配后不再变化），使得每个机器人都能按时充电，且所有充电站的使用率尽可能平均。

一个充电站的负载率指使用该充电站给机器人充电的时长在总时长的比率，负载率可以由分配给它的所有机器人的 $c_i / t_i$ 之和来计算。负载率不能超过 $100\%$。

请计算在最优安排下，$k$ 个充电站的最大负载率（定义为使用率最高的充电站的使用百分比）的最小可能值。

输入格式

输入的第一行包含两个正整数 $n, k$，用一个空格分隔，分别表示机器人种类数和充电站数量。

接下来 $n$ 行，每行包含两个正整数 $t_i, c_i$，用一个空格分隔，分别表示第 $i$ 种机器人的工作周期和充电时间。

接下来 $n$ 行，每行包含一个整数 $r_i$，表示第 $i$ 种机器人的数量。

输出格式

输出一行包含一个整数表示答案，即最小可能的最大负载率，以百分比表示，先转化为百分比之后，再四舍五入取整到最接近的整数。

1 6
9 1
5

11

4 2
9 3
8 1
7 1
7 4
2
2
1
1

82

提示

样例说明 1

有 $5$ 个同规格的机器人和 $6$ 个充电站，因此我们可以为每个机器人分配一个充电站，此时充电站的最大使用率为 $1/9 = 0.1111\ldots$，转为百分比为 $11.11\ldots$。

样例说明 2

按照上表的分配方案，充电站 1 的负载率为 $3/9 + 3/9 + 1/7 = 0.8095\ldots$，转为百分比再四舍五入后为 $81\%$；

充电站 2 的负载率为 $1/8 + 1/8 + 4/7 = 0.8214\ldots$，转为百分比再四舍五入后为 $82\%$；因此答案为 $82$。

评测用例规模与约定

对于 $20\%$ 的评测用例，$1 \le n, k \le 5$，$1 \le r_i \le 3$；

对于 $60\%$ 的评测用例，$1 \le n, k \le 5$，$1 \le r_i \le 5$；

对于所有评测用例，$1 \le n, k \le 10$，$1 \le t_i, c_i \le 1000$，$1 \le r_i \le 10$。