Problem Description

Xiao Lan plans to buy $n$ types of items, and he needs $1$ of each type.

There are $m$ shops near where Xiao Lan lives, and each shop sells various items.

Shop $i$ offers a discount from day $s_i$ to day $t_i$, with a discount rate $p_i$. For an item with original price $b$, the discounted price is $\lfloor\frac {b\cdot p_j}{100}\rfloor$. At other times, the item must be bought at the original price.

Xiao Lan is very busy, so he can only choose one day to buy all the items. What is the minimum amount of money he needs to spend to buy all the required items.

It is guaranteed that Xiao Lan can buy all the items he needs.

Input Format

The first line contains two integers $n, m$, separated by a space, representing the number of item types and the number of shops.

Next come the descriptions of the shops in order. Each shop consists of several lines. The first line contains four integers $s_i, t_i, p_i, c_i$, separated by spaces, representing the start and end time of the shop’s discount, the discount rate, and the total number of products in the shop. Then follow $c_i$ lines, each containing two integers $a_j, b_j$, separated by a space, representing the type and the price of the $j$-th product in the shop. Item types are numbered from $1$ to $n$.

Output Format

Output one line containing one integer, indicating the minimum amount of money Xiao Lan needs to spend.

2 2
1 2 89 1
1 97
3 4 77 1
2 15

101

Hint

For $40\%$ of the testdata, $n, m \le 500$, $s_i \le t_i \le 100$, $\sum c_i \le 2000$.

For $70\%$ of the testdata, $n, m \le 5000$, $\sum c_i \le 20000$.

For all testdata, $1 \le n, m \le 10^5$, $1 \le c_i \le n$, $\sum c_i \le 4\times10^5$, $1 \le s_i \le t_i \le 10^9$, $1 < p_i < 100$, $1 \le a_j \le n$, $1 \le b_j \le 10^9$.

Lanqiao Cup 2022 National Contest, Group C, Problem I.

Translated by ChatGPT 5