Problem Description

A logistics company uses $n$ different models of robots to work in a warehouse. A robot can start charging at any time; it does not need to wait until the battery is completely drained. Likewise, charging can end at any time; it does not need to wait until the battery is full. The only requirement is to ensure that, within any continuous $t_i$ minutes, each robot can obtain a total of $c_i$ minutes of charging time.

The company plans to set up $k$ charging stations in the warehouse. A charging station can charge any model of robot, and each charging station can charge only one robot at any moment. Except for charging time, robots are running at all other times. To ensure operating efficiency, the company wants to arrange a charging schedule and assign each robot to exactly one charging station (the assignment does not change after being made), so that every robot can be charged on time, and the utilization of all charging stations is as balanced as possible.

The load rate of a charging station is defined as the ratio of the time this station is used to charge robots to the total time. The load rate can be calculated as the sum of $c_i / t_i$ over all robots assigned to it. The load rate must not exceed $100\%$.

Compute, under the optimal arrangement, the minimum possible value of the maximum load rate among the $k$ charging stations (that is, the usage percentage of the most heavily used charging station).

Input Format

The first line contains two positive integers $n, k$, separated by a space, representing the number of robot models and the number of charging stations.

The next $n$ lines each contain two positive integers $t_i, c_i$, separated by a space, representing the working cycle and the charging time of the $i$-th robot model.

The next $n$ lines each contain an integer $r_i$, representing the number of robots of the $i$-th model.

Output Format

Output one line containing an integer, which is the answer: the minimum possible maximum load rate, expressed as a percentage. Convert it to a percentage first, then round to the nearest integer.

1 6
9 1
5

11

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

82

Hint

Sample Explanation 1

There are $5$ robots of the same specification and $6$ charging stations, so we can assign one charging station to each robot. In this case, the maximum utilization of the charging stations is $1/9 = 0.1111\ldots$, which becomes $11.11\ldots$ as a percentage.

Sample Explanation 2

According to the assignment plan in the table above, the load rate of station 1 is $3/9 + 3/9 + 1/7 = 0.8095\ldots$, which becomes $81\%$ after converting to a percentage and rounding;

The load rate of station 2 is $1/8 + 1/8 + 4/7 = 0.8214\ldots$, which becomes $82\%$ after converting to a percentage and rounding. Therefore, the answer is $82$.

Constraints and Notes on Testdata

For $20\%$ of the testdata, $1 \le n, k \le 5$, $1 \le r_i \le 3$.

For $60\%$ of the testdata, $1 \le n, k \le 5$, $1 \le r_i \le 5$.

For all testdata, $1 \le n, k \le 10$, $1 \le t_i, c_i \le 1000$, $1 \le r_i \le 10$.

Translated by ChatGPT 5