取餐 - 代码源竞赛平台

题目描述

一家餐厅按顺序摆放了 $n$ 道菜，编号为 $1,2,\ldots,n$。共有 $m$ 位顾客依次取餐，按取餐顺序编号为 $1,2,\ldots,m$。每位顾客都会从第 $1$ 道菜取到第 $n$ 道菜，每道菜恰好取一份，最后结账。

第 $i$ 道菜的原价为 $p_i$ 元，折扣价为 $d_i$ 元，其中 $0\le d_i\le p_i$。餐厅对每道菜分别规定一个整数 $t_i$：前 $t_i$ 位顾客取这道菜时支付原价，其余顾客支付折扣价。

也就是说，第 $j$ 位顾客购买第 $i$ 道菜的价格为：

• 若 $j\le t_i$，则支付 $p_i$ 元；
• 若 $j>t_i$，则支付 $d_i$ 元。

请求出每位顾客需要支付的总金额。

输入格式

第一行包含两个正整数 $n,m$，分别表示菜品数量和顾客数量。

接下来 $n$ 行，第 $i$ 行包含三个整数 $p_i,d_i,t_i$，分别表示第 $i$ 道菜的原价、折扣价和需要支付原价的顾客数量。

输出格式

输出一行，包含 $m$ 个整数，依次表示第 $1,2,\ldots,m$ 位顾客需要支付的总金额。

样例

3 5
10 6 2
8 3 0
5 2 4

18 18 14 14 11

2 3
7 0 0
4 1 3

4 4 4

样例解释

对于样例 $1$，第 $1,2$ 位顾客均需支付 $10+3+5=18$ 元，第 $3,4$ 位顾客均需支付 $6+3+5=14$ 元，第 $5$ 位顾客需支付 $6+3+2=11$ 元。

对于样例 $2$，第一道菜从第 $1$ 位顾客起就使用折扣价，每份为 $0$ 元；第二道菜对全部 $3$ 位顾客均使用原价，每份为 $4$ 元。因此每位顾客都需支付 $4$ 元。

数据规模

本题各子任务单独计分。须通过某子任务包含的所有测试点，方可获得该子任务的分数。

子任务编号	分数	$n\le$	$m\le$
$1$	$30$	$2000$	$2000$
$2$	$70$	$2\times 10^5$	$2\times 10^5$

对于 $100\%$ 的数据，$1\le n,m\le 2\times 10^5$，$0\le d_i\le p_i\le 10^9$，$0\le t_i\le m$。