机械加工

题目描述

马二狗以绝对的实力稳坐马布斯富豪榜的第一名，本月马二狗又又又新开了一家机械加工厂。由于马二狗的口碑非常好，所以很快就收到了一张订单，订单要求在 T 天后需要提供 m 件加工后的产品。

马二狗需要在这些天中，收购原材料并加工生产，一件原材料可加工生产一件产品，以便于在 T 天后完成这张订单。生产产品的成本来自两个方面：

• 材料费：原材料的价格会变化，在 T 天中，只有 n 天能够收购原材料。其中，第 i 次能够买到的原材料是在第 $d_i$ 天，这一天能提供的原材料共 $w_i$ 件，每件原材料的价格为 $p_i$ 元。
• 存储费：需要对原材料或产品进行保养，每件原材料或产品每天存储费用是 k（0 ≤ k ≤ 1）元。

你作为马二狗的强力助手，请你帮助马二狗计算如何安排原材料购买计划，能够使得完成这张订单的成本最小。

输入描述

第一行包含四个整数 T、m、n、k。

接下来 n 行，每行三个整数 $d_i$、$w_i$、$p_i$，第 i 行表示第 i 次能够买原料的日期、数量和单价。

输出描述

一行一个整数，表示答案。数据保证一定存在满足要求的结果。

样例 1

输入：

15 10 3 0
2 5 6
5 3 8
8 6 7

输出：

65

样例 1 解释：一共需要 10 件产品，存储费是 0 元。在第 2 天购买 5 件原材料，材料费 5×6=30，存储费 0 元，共计 30 元。在第 8 天购买 5 件原材料，材料费 5×7=35，存储费 0 元，共计 35 元。因此，总计需要 65 元。

样例 2

输入：

15 10 3 1
2 5 6
5 3 8
8 6 7

输出：

157

样例 2 解释：一共需要 10 件产品，存储费是 1 元。在第 2 天购买 1 件原材料，材料费 1×6=6，1 件存储 13 天，存储费 13 元，共计 19 元。在第 5 天购买 3 件原材料，材料费 3×8=24，3 件存储 10 天，存储费 30 元；原始题面把这一项写作“共计 52 元”，实际相加为 54 元。在第 8 天购买 6 件原材料，材料费 6×7=42，6 件存储 7 天，存储费 42 元，共计 84 元。因此，总计需要 157 元。

输入样例 #3

644 12 3 0
470 8 59
386 39 59
99 7 98

输出样例 #3

708

数据范围

对 100% 的数据保证：1 ≤ T、m ≤ 10^6，1 ≤ n ≤ 2×10^5，1 ≤ $d_i$ < T，1 ≤ $w_i$、$p_i$ ≤ 10^6，0 ≤ k ≤ 1。原始 HTML 的日期限制写成 1≤d_i,n<T，此处按上下文明确日期下标为 i。