#8944. 「THUPC 2025 初赛」 骑行计划 省选/NOI−

随着盛夏的到来，小 Rei 迎来了长达 天的假期。为了充分利用这段时间，她计划每天骑共享单车出门，享受户外的清新空气。根据小 Rei 的计划，第 天她将会骑行 分钟，而每分钟的骑行费用为 元。

为了节约开支，小 Rei 打算购买 APP 中提供的一些骑行卡。她了解到现在有 种骑行卡可以购买，其中第 种骑行卡的具体信息如下：

• 售价 ：每张卡的价格为 元；
• 有效期 ：从购买当天算起，连续 天内有效；
• 免费时间 ：在有效期内，每天的前 分钟骑行是免费的。

小 Rei 可以多次购买任意一种骑行卡，并且可以在同一时间持有多张有效的骑行卡。如果某天有多张骑行卡同时有效，那么当天可以享受的免费骑行时间为这些卡中 的最大值。超出免费时间的部分，仍然按照每分钟 元计算。

小 Rei 希望在假期中尽可能减少骑行的总支出。请你帮助她计算出在假期中骑行的最小总支出是多少。

第一行包含三个整数 ，分别表示假期的天数，骑行卡的种类数以及每分钟的骑行费用。

第二行包含 个整数，第 个整数表示第 天骑行的分钟数 。

接下来的 行，每行包含三个整数 ，分别表示第 种骑行卡的售价，有效期天数以及免费骑行时间。

输出一个整数，表示小 Rei 在假期中骑行的最小总支出。

样例输入 1

复制5 2 2
30 40 50 20 10
10 3 20
15 2 30

样例输出 1

复制100

样例输入 2

复制8 4 1
5 10 9 3 9 8 3 1
11 4 5
12 7 4
10 2 9
5 3 4

样例输出 2

复制33

样例 1 解释

小 Rei 的最优策略为：在第一天和第二天购买第二种骑行卡，在第三天购买第一种骑行卡。此时前三天的免费时间为 分钟，后两天的免费时间为 分钟，还需要在第二天额外支付 分钟的骑行费用，在第三天额外支付 20 分钟的骑行费用。购买骑行卡共花费 元，额外骑行费用为 元，总支出为 元。可以证明不存在总支出更少的方案，故输出 。

题目来源

来自 2025 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2025）初赛。

题解等资源可在 https://gitlink.org.cn/thusaa/thupc2025pre/tree/master 查看。