{"problem":{"name":"[蓝桥杯 2022 国 C] 打折","description":{"content":"小蓝打算采购 $n$ 种物品，每种物品各需要 $1$ 个。 小蓝所住的位置附近一共有 $m$ 个店铺，每个店铺都出售着各种各样的物品。 第 $i$ 家店铺会在第 $s_i$ 天至第 $t_i$ 天打折，折扣率为 $p_i$，对于原件为 $b$ 的物品，折后价格为 $\\lfloor\\frac {b\\cdot p_j}{100}\\rfloor$。其它时间需按原价购买。 小蓝很忙，他只能选择一天的","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8812"},"statements":[{"statement_type":"Markdown","content":"小蓝打算采购 $n$ 种物品，每种物品各需要 $1$ 个。\n\n小蓝所住的位置附近一共有 $m$ 个店铺，每个店铺都出售着各种各样的物品。\n\n第 $i$ 家店铺会在第 $s_i$ 天至第 $t_i$ 天打折，折扣率为 $p_i$，对于原件为 $b$ 的物品，折后价格为 $\\lfloor\\frac {b\\cdot p_j}{100}\\rfloor$。其它时间需按原价购买。\n\n小蓝很忙，他只能选择一天的时间去采购这些物品。请问，他最少需要花多少钱才能买到需要的所有物品。\n\n题目保证小蓝一定能买到需要的所有物品。\n\n## Input\n\n输入的第一行包含两个整数 $n,m$，用一个空格分隔，分别表示物品的个数和店铺的个数。\n\n接下来依次包含每个店铺的描述。每个店铺由若干行组成，其中第一行包含四个整数 $s_i,t_i, p_i,c_i$，相邻两个整数之间用一个空格分隔，分别表示商店优惠的起始和结束时间、折扣率以及商店内的商品总数。之后接 $c_i$ 行，每行包含两个整数 $a_j,b_j$，用一个空格分隔，分别表示该商店的第 $j$ 个商品的类型和价格。商品的类型由 $1$ 至 $n$ 编号。\n\n## Output\n\n输出一行包含一个整数表示小蓝需要花费的最少的钱数。\n\n[samples]\n\n## Note\n\n对于 $40\\%$ 的评测用例，$n,m≤500，s_i ≤t_i ≤100，\\sum c_i ≤2000$；\n\n对于 $70\\%$ 的评测用例，$n,m≤5000，\\sum c_i ≤20000$；\n\n对于所有评测用例，$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$。\n\n蓝桥杯 2022 国赛 C 组 I 题。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8812","tags":["2022","枚举","差分","蓝桥杯国赛"],"sample_group":[["2 2\n1 2 89 1\n1 97\n3 4 77 1\n2 15","101"]],"created_at":"2026-03-03 11:09:25"}}