题目描述

小蓝打算采购 $n$ 种物品，每种物品各需要 $1$ 个。

小蓝所住的位置附近一共有 $m$ 个店铺，每个店铺都出售着各种各样的物品。

第 $i$ 家店铺会在第 $s_i$ 天至第 $t_i$ 天打折，折扣率为 $p_i$，对于原件为 $b$ 的物品，折后价格为 $\lfloor\frac {b\cdot p_j}{100}\rfloor$。其它时间需按原价购买。

小蓝很忙，他只能选择一天的时间去采购这些物品。请问，他最少需要花多少钱才能买到需要的所有物品。

题目保证小蓝一定能买到需要的所有物品。

输入格式

输入的第一行包含两个整数 $n,m$，用一个空格分隔，分别表示物品的个数和店铺的个数。

接下来依次包含每个店铺的描述。每个店铺由若干行组成，其中第一行包含四个整数 $s_i,t_i, p_i,c_i$，相邻两个整数之间用一个空格分隔，分别表示商店优惠的起始和结束时间、折扣率以及商店内的商品总数。之后接 $c_i$ 行，每行包含两个整数 $a_j,b_j$，用一个空格分隔，分别表示该商店的第 $j$ 个商品的类型和价格。商品的类型由 $1$ 至 $n$ 编号。

输出格式

输出一行包含一个整数表示小蓝需要花费的最少的钱数。

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

101

提示

对于 $40\%$ 的评测用例，$n,m≤500，s_i ≤t_i ≤100，\sum c_i ≤2000$；

对于 $70\%$ 的评测用例，$n,m≤5000，\sum c_i ≤20000$；

对于所有评测用例，$1 ≤ n,m ≤ 10^5，1 ≤ c_i ≤ n，\sum c_i ≤ 4\times10^5，1 ≤ s_i ≤t_i ≤10^9，1 < p_i < 100，1≤a_j ≤n，1≤b_j ≤10^9$。

蓝桥杯 2022 国赛 C 组 I 题。