Balatro

Cards are arranged in a row. Each card has a value and is one of two types: an add card (a) or a multiply card (m).

The score is computed as follows. The initial score is 0. Process the cards from left to right.

• If the card is an add card, increase the score by the card's value.
• If the card is a multiply card, multiply the score by the card's value.

The final score is the score after all cards are processed.

For each subsequence size, find the maximum score you can get from a subsequence of that size. If the limit on multiply cards makes that size impossible, find the maximum score for the largest possible size below it. The chosen cards keep their original order, and you cannot rearrange them. A subsequence does not have to be contiguous.

The first line contains two integers $n$ ($2≤n≤2 \cdot10^5$) and $k$ ($0≤k≤n$), where $n$ is the number of cards and $k$ is the maximum number of multiply cards you can use.

Each of the next $n$ lines contains a letter $s$ and an integer $v$. $s$ is either a (add card) or m (multiply card), and $v$ is the card's value ($2≤v≤1\,000$).

The product of all multiply card values is at most $10^9$.

Output $n$ lines. The $i$-th line contains the maximum score for a subsequence of length at most $i$, for $i$ from 1 to $n$.