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 $$$3N$$$, inclusive.

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