这题贪心（std 是贪心）假了，数据太大 DP 过不了，所以求正解。

要求如下：

能 AC 本题并且能通过 Hack 数据的代码。

Hack 数据：

输入

4 3 3
1 1 10000 14000
50 70 70

输出

11862