34739번 - Horrible Restaurants 다국어

문제

Ricardo is a restaurant critic, which means he spends his time eating at restaurants and giving them a rating. Each rating is an integer number of stars between 0ドル$ and 3ドル,ドル inclusive. Thus, there are exactly four possible ratings.

During his visit to Cheapland, he must review $N$ restaurants. Unfortunately, all of them are terrible, and if left to his honest opinion, Ricardo would give 0ドル$ stars to every restaurant. However, the government of Cheapland can bribe Ricardo to increase the rating of any restaurant.

Each restaurant has its own bribe costs, which depend both on the restaurant itself and on the number of stars awarded. Bribing Ricardo to give a restaurant 3ドル$ stars is always more expensive than bribing him for 2ドル$ stars, which in turn is more expensive than bribing him for 1ドル$ star. Naturally, no payment is required for a 0ドル$-star rating.

As one might imagine, the Cheapland government wants to spend as little as possible while making their gastronomic scene look as strong as possible. To plan their strategy, they need to determine the minimum cost required to achieve a total of $k$ stars among all the $N$ restaurants, for every integer value $k$ between 1ドル$ and 3ドルN,ドル inclusive.

However, since bribe costs vary from restaurant to restaurant, calculating these values isn’t straightforward – which is why they need your help.

입력

The first line contains an integer $N$ (1ドル ≤ N ≤ 2 \cdot 10^5 $) indicating the number of restaurants.

Each of the next $N$ lines describes a restaurant with three integers $C_1,ドル $C_2$ and $C_3$ (1ドル ≤ C_1 < C_2 < C_3 ≤ 10^9 $), where $C_i$ is the cost of getting a rating of $i$ stars for the restaurant.

출력

Output a line for each $k$ from 1ドル$ to 3ドルN$ (inclusive), with an integer indicating the minimum total cost required to achieve exactly $k$ stars among all the $N$ restaurants.

제한

노트