{"problem":{"name":"[SHUPC 2024] 为美好的世界献上爆焰！","description":{"content":"具体来说，魔王城的结界护盾共有 $x$ 的血量，小 A 想在 $n$ 天内完成对魔王城护盾的破坏。每天小 B 的魔力值会恢复至 $m$ ，且魔力值的上限为 $M$ ，使用爆裂魔法时每 $1$ 点魔力值可以对魔王城护盾造成 $1$ 点伤害。当然，爆裂魔法每天只能使用一次。 为了确保小 B 可以造成充足的伤害，小 A 每天可以花钱去商店购买魔晶石为小 B 增加魔力值。但是商店每天出售的魔晶石的数量、","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10316"},"statements":[{"statement_type":"Markdown","content":"具体来说，魔王城的结界护盾共有 $x$ 的血量，小 A 想在 $n$ 天内完成对魔王城护盾的破坏。每天小 B 的魔力值会恢复至 $m$ ，且魔力值的上限为 $M$ ，使用爆裂魔法时每 $1$ 点魔力值可以对魔王城护盾造成 $1$ 点伤害。当然，爆裂魔法每天只能使用一次。\n\n为了确保小 B 可以造成充足的伤害，小 A 每天可以花钱去商店购买魔晶石为小 B 增加魔力值。但是商店每天出售的魔晶石的数量、价格、和魔力值都有所不同。且当天出售的**魔晶石只能当天使用**，不然会过期，无法补充魔力。小A现在想知道，如果要小 B 能够顺利爆破魔王城的护盾，最少需要花费多少钱？（如果无法完成破坏，则输出 `-1`）\n\n**注意**：由于小 B 的魔力值具有上限，因此当魔晶石魔力含量 $h$ 加上小 B 当前魔力值 $m$ 大于等于 $M$ 时，使用该魔晶石只能使小 B 的魔力值变为 $M$ ，也就是说 $ m'=\\min(M,m+h)$ 。\n\n## Input\n\n第一行输入四个正整数，$n,x,M,m$ （$1 \\le n,x,M \\le 5000,m \\le M$）。\n\n接下来会有 $n$ 组数据，每组数据有三行。\n\n第一行代表第 $i$ 天出售的魔晶石数量 $\\text{num}_i\\ (1 \\le \\text{num} \\le 5000)$ ，数据保证 $\\sum_{i=1}^{n}\\text{num}_i\\le 5000$。\n\n第二行共 $\\text{num}_i$ 个正整数，代表第 $i$ 天出售的第 $j$ 个魔晶石的价格 $p_{i,j}\\ (1\\le p_{i,j} \\le 10^9)$ 。\n\n第三行共 $\\text{num}_i$ 个正整数，代表第 $i$ 天出售的第 $j$ 个魔晶石的魔力值 $h_{i,j}\\ (1 \\le h_{i,j} \\le M)$ ，数据保证 $\\sum_{i=1}^{n}\\sum_{j=1}^{\\text{num}_i}h_{i,j}\\le 5000$。\n\n## Output\n\n输出一个整数，代表所求的答案。\n\n[samples]\n\n## Background\n\n小 A 目前正在带着小 B 进行攻打魔王城的每日一爆演练。\n\n## Note\n\n样例解释：\n\n样例 1 中，可以选择购买第一天的第一个魔晶石，花费为 $1$，当天总魔力值为 $8$。再购买第二天的第一个魔晶石，花费为 $1$，当天总魔力值为 $9$。这样两天总共可以造成 $17$ 点伤害，成功破坏结界，且花费最少为 $2$。\n\n样例 2 中，因为存在魔力值上限，因此第一天最多造成 $10$ 点伤害，而第二天最多造成 $9$ 点伤害，因此无法破坏结界。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10316","tags":["2024","高校校赛"],"sample_group":[["2 17 10 6\n3\n1 1 2\n2 1 7\n2\n1 2\n3 4","2"],["2 20 10 8\n3\n10 2 3\n8 2 1\n1\n1\n1","-1"],["2 17 10 9\n3\n1 1 2\n2 2 7\n2\n1 2\n3 4","0"]],"created_at":"2026-03-03 11:09:25"}}