题目描述

给定一排卡牌。每张卡牌有一个数值，并且属于两种类型之一：

• a：加法牌；
• m：乘法牌。

一排卡牌的分数按如下方式计算：初始分数为 $0$，然后从左到右依次处理卡牌。

• 如果当前卡牌是加法牌，则将分数增加该卡牌的数值；
• 如果当前卡牌是乘法牌，则将分数乘以该卡牌的数值。

处理完所有选中的卡牌后得到最终分数。

现在对于每一种可能的子序列长度上限，你都想知道：在保持原相对顺序的前提下，选取长度不超过该上限的子序列，并且使用的乘法牌数量不超过 $k$，最多能得到多少分。

注意：

• 选出的卡牌不能重新排序；
• 子序列不要求连续；
• 若由于乘法牌数量限制，无法达到某个长度，也允许选取更短的子序列。

输入格式

第一行包含两个整数 $n,k$，其中：

• $2 \le n \le 2\cdot 10^5$，表示卡牌数量；
• $0 \le k \le n$，表示最多可以使用的乘法牌数量。

接下来 $n$ 行，每行包含一个小写字母 $s$ 和一个整数 $v$。

• $s$ 为 a 或 m，分别表示加法牌或乘法牌；
• $2 \le v \le 1000$，表示该卡牌的数值。

保证所有乘法牌数值的乘积不超过 $10^9$。

输出格式

输出 $n$ 行。

第 $i$ 行输出在选取子序列长度不超过 $i$ 时，能够得到的最大分数。

样例 #1

输入 #1

4 3
a 3
m 2
a 8
m 3

输出 #1

8
24
33
42

样例 #2

输入 #2

6 1
a 2
m 5
a 2
a 2
m 3
a 3

输出 #2

3
10
13
18
21
21