给定两个仅由字符 $$$\{\texttt{a}, \texttt{b}, \texttt{c}\}$$$ 组成的字符串 $$$S$$$ 和 $$$T$$$。你可以对字符串 $$$S$$$ 进行任意次（包括零次）以下操作：
- 选择 $$$S$$$ 中的一个字符 a，将其替换为 bc；
- 选择 $$$S$$$ 中的一个字符 b，将其替换为 ca；
- 选择 $$$S$$$ 中的一个字符 c，将其替换为 ab；
- 选择 $$$S$$$ 中相邻的两个相同字符，将它们一并删除。
现在，你需要回答在字符串 $$$T$$$ 中，有多少个不同的子串能够由初始串 $$$S$$$ 经过有限次上述操作后得到。
这里，字符串 $$$T$$$ 的子串定义为 $$$T$$$ 中连续的一段字符序列，即对于下标 $$$l, r$$$ $$$(1 \le l \le r \le |T|)$$$，子串表示为 $$$T_l T_{l+1} \dots T_r$$$。需要注意的是，两个子串被认为是不同的，当且仅当它们在 $$$T$$$ 中对应的下标区间不同；即使两个子串的字符序列完全相同，只要它们的位置不同，就会被视作不同的子串。
第一行输入一个整数 $$$t$$$ $$$(1 \le t \le 10^5)$$$，表示测试数据组数。
接下来 $$$2t$$$ 行，每两组数据包含以下两行：
- 第一行输入一个字符串 $$$S$$$。
- 第二行输入一个字符串 $$$T$$$。
保证所有字符串均只由小写字母 a、b、c 构成。保证所有测试数据中，$$$\sum |S| \le 2 \times 10^6$$$ 且 $$$\sum |T| \le 2 \times 10^6$$$。
对于每组测试数据，输出一行一个整数，表示 $$$T$$$ 中能够由 $$$S$$$ 经过操作得到的子串的个数。
1aaabc
4
对于唯一的测试数据，初始串 $$$S = \texttt{"a"}$$$：
- 不进行任何操作，可得到串 "a"，它对应 $$$T$$$ 中两个不同位置的子串：$$$T[1,1] = \texttt{"a"}$$$ 和 $$$T[2,2] = \texttt{"a"}$$$；
- 对唯一的 "a" 执行一次替换为 "bc" 的操作，得到串 "bc"，它对应 $$$T[3,4] = \texttt{"bc"}$$$；
- 在上一步得到 "bc" 后，可继续操作（具体操作序列略），最终可得到串 "aabc"，对应 $$$T[1,4] = \texttt{"aabc"}$$$。
因此符合条件的子串共 $$$4$$$ 个：$$$T[1,1]$$$、$$$T[2,2]$$$、$$$T[3,4]$$$、$$$T[1,4]$$$。
在上一轮的星际战争中，总司令因为错误的情报遭遇大败。现在他希望你帮他逃出生天。
星际战场可以看成一个二维平面。总司令的位置是一个非负整数坐标 $$$(x_a, y_a)$$$，敌人的位置也是一个非负整数坐标 $$$(x_b, y_b)$$$。总司令希望安全抵达位于原点 $$$(0,0)$$$ 的虫洞，不幸的是，敌人正在追捕他，并且同样以 $$$(0,0)$$$ 为目标。
因为星际航路限制，每次移动只能将当前坐标 $$$(x, y)$$$ 变为 $$$(x-1, y)$$$ 或 $$$(x, y-1)$$$，且移动后的坐标必须保持非负。
敌人的舰队有一个强大的能力：空间陷阱。敌人会在其初始位置以及每次移动后所到达的每一个新位置（原点除外）立刻部署空间陷阱，总司令身处空间陷阱就会被抓住。幸运的是，虫洞所在的 $$$(0,0)$$$ 因为时空畸变，并不能部署空间陷阱。此外，只要总司令移动到 $$$(0,0)$$$，无论敌人身在何处（包括原点），总司令都会立刻成功撤离。
敌人率先采取行动，随后双方轮流移动。双方都足够聪明，会在行动中做出最优选择，并且任何一方都不能跳过自己的回合。特别地，总司令在移动时不能进入任何已被部署空间陷阱的位置（包括敌人当前所在位置，除非敌人已经到达原点），否则将被立即捕获。
给定初始坐标 $$$(x_a, y_a)$$$ 与 $$$(x_b, y_b)$$$，判断总司令能否成功撤离。
第一行输入一个整数 $$$T$$$ $$$(1 \le T \le 10^6)$$$，表示测试数据组数。
接下来 $$$T$$$ 行，每行输入四个整数 $$$x_a, y_a, x_b, y_b$$$ $$$(0 \le x_a, y_a, x_b, y_b \le 10^9, (x_a, y_a) \neq (x_b, y_b))$$$，分别表示总司令和敌人的初始坐标。
注意：本题输入数据规模较大，建议使用较快的 I/O 方式。
对于每组测试数据，输出一行一个字符串：若总司令有必胜策略则输出 YES，否则输出 NO。
41 1 2 21 1 2 10 3 1 00 3 1 1
YES NO YES NO
第二组数据：敌人先手直接移动到 $$$(1,1)$$$，此处成为空间陷阱，总司令立即失败。
第三组数据：敌人无法在原点部署空间陷阱，总司令可直接抵达虫洞，成功撤离。
请你构造一个 $$$0$$$ 到 $$$n-1$$$ 的排列 $$$a$$$，以最小化相邻元素的异或值之积，即最小化以下表达式： $$$$$$\prod_{i=1}^{n-1} (a_i \oplus a_{i+1})$$$$$$ 如果有多个序列满足条件，请输出字典序最小的那个。
第一行输入一个整数 $$$t$$$ $$$(1 \le t \le 10^3)$$$，表示测试用例的数量。
接下来 $$$t$$$ 行，每行输入一个整数 $$$n$$$ $$$(1 \le n \le 2 \times 10^6)$$$，表示排列的长度。
保证所有测试用例中 $$$n$$$ 的总和不超过 $$$2 \times 10^6$$$。
对于每个测试用例，输出一行 $$$n$$$ 个整数，表示满足条件的排列。
234
1 0 2 0 1 3 2
对于第二组样例，排列 $$$0,1,3,2$$$ 的相邻异或值分别为 $$$0 \oplus 1 = 1$$$、$$$1 \oplus 3 = 2$$$、$$$3 \oplus 2 = 1$$$， 因此乘积为 $$$1 \times 2 \times 1 = 2$$$。 可以证明不存在乘积更小的排列。
给定一个长度为 $$$n$$$ 的整数序列 $$$A = (a_1, a_2, \ldots, a_n)$$$。定义函数 $$$T(B)$$$ 如下：
对于任意长度为偶数的序列 $$$B$$$，Alice 和 Bob 轮流从中删除一个数（Alice 先手），直到剩下两个数。Alice 希望最后剩下的两个数的差的绝对值尽可能小，Bob 希望尽可能大。在双方均采取最优策略的前提下，记 $$$T(B)$$$ 为最终剩下的两个数的差的绝对值。
你需要维护序列 $$$A$$$，并按顺序处理以下两种操作：
- 修改：给定下标 $$$i$$$，将 $$$a_i$$$ 的值增加 $$$1$$$。
- 变换：给定整数 $$$t$$$，对序列 $$$A$$$ 中的所有元素执行变换： $$$$$$ a_i \leftarrow \begin{cases} a_i - t, & \text{if } a_i \gt t \\ t, & \text{if } a_i \le t \end{cases} $$$$$$
你需要按顺序处理这些操作，并在初始时以及每次操作后，输出当前序列 $$$A$$$ 对应的 $$$T(A)$$$ 的值。
第一行输入两个整数 $$$n, q$$$ $$$(2 \le n \le 2 \times 10^5, 1 \le q \le 2 \times 10^5)$$$，分别表示序列长度和操作次数。保证 $$$n$$$ 为偶数。
第二行输入 $$$n$$$ 个整数 $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \le a_i \le 10^8)$$$，表示初始序列。
接下来 $$$q$$$ 行，每行描述一个操作：
- 1 i：表示执行修改操作，将 $$$a_i$$$ 增加 $$$1$$$ $$$(1 \le i \le n)$$$。
- 2 t：表示执行变换操作，对序列执行参数为 $$$t$$$ 的变换 $$$(1 \le t \le 10^8)$$$。
输出共 $$$q + 1$$$ 行，每行一个整数。第 $$$1$$$ 行表示初始序列的 $$$T(A)$$$ 值。
接下来第 $$$2$$$ 到第 $$$q + 1$$$ 行依次表示每次操作后的 $$$T(A)$$$ 值。
6 31 3 6 5 4 91 32 31 4
3 4 2 1
Asrit wants to fry beef. He has a large pan that can hold at most $$$n$$$ pieces of beef at the same time.
The rules for frying the beef are as follows:
- Each piece of beef has $$$k$$$ sides.
- It takes exactly $$$1$$$ second to cook any side.
- Flipping takes no extra time.
Specifically, a piece of beef can be picked up or put down at any time. If not all $$$k$$$ sides of a piece of beef are cooked, it can be temporarily removed from the pan and put back later to continue cooking the uncooked sides.
Now, Asrit wants to cook a total of $$$m$$$ pieces of beef. Please help him calculate the minimum number of seconds required.
The first line of input contains three integers $$$n, m, k$$$ $$$(1 \le n, k \le 10^6, 1 \le m \le 10^{10})$$$, representing the maximum number of pieces of beef the pan can hold simultaneously, the total number of pieces of beef to be cooked, and the number of sides of each piece of beef, respectively.
Output a single integer on one line, representing the minimum number of seconds required to cook all the beef.
2 3 2
3
给定一个长度为 $$$n$$$ 的排列 $$$a_1, a_2, \dots, a_n$$$。为了方便描述边界情况，我们定义 $$$a_0 = 0$$$ 且 $$$a_{n+1} = 0$$$。
你可以对该序列进行无限次操作（包括零次）。每次操作的具体规则如下：
- 选择一个区间 $$$[l, r]$$$ $$$(1 \le l \le r \le n)$$$。
- 该区间必须满足条件：区间内的所有元素都严格大于区间外侧紧邻的边界元素，即对于 $$$\forall i \in [l, r]$$$，均有 $$$a_i \gt \max(a_{l-1}, a_{r+1})$$$。
- 将选定的区间 $$$[l, r]$$$ 进行翻转。即把序列由： $$$$$$ a_1, \dots, a_{l-1}, \underbrace{a_l, a_{l+1}, \dots, a_{r-1}, a_r}_{\text{区间 } [l, r]}, a_{r+1}, \dots, a_n $$$$$$ 变为： $$$$$$ a_1, \dots, a_{l-1}, \underbrace{a_r, a_{r-1}, \dots, a_{l+1}, a_l}_{\text{翻转后的区间 } [l, r]}, a_{r+1}, \dots, a_n $$$$$$
请你求出，经过任意次合法操作后，表达式 $$$\sum_{i=1}^n i \times a_i$$$ 所能取到的最大值和最小值。
第一行输入一个正整数 $$$n$$$ $$$(1 \le n \le 2 \times 10^5)$$$，表示排列的长度。
第二行输入 $$$n$$$ 个正整数 $$$a_1, a_2, \dots, a_n$$$，表示给定的排列。
输出一行两个正整数，用空格隔开，分别表示给定序列经过操作后 $$$\sum_{i=1}^n i \times a_i$$$ 的最大值和最小值。
64 3 1 5 2 6
80 67
对于给定的初始序列 $$$[4, 3, 1, 5, 2, 6]$$$：
- 求最大值：可以通过操作 $$$[4, 3, 1, 5, 2, 6] \to [3, 4, 1, 5, 2, 6]$$$，由此得到最大值。
- 求最小值：可以通过操作 $$$[4, 3, 1, 5, 2, 6] \to [6, 2, 5, 1, 3, 4] \to [6, 2, 5, 1, 4, 3]$$$，由此得到最小值。
给定一个由小写字母组成的字符串 $$$s$$$。对于该字符串，我们记其长度为 $$$|s|$$$，记其反串为 $$$s^R$$$（即将 $$$s$$$ 左右颠倒后得到的字符串）。同时，我们用 $$$\operatorname{prefix}(s, i)$$$ 表示由 $$$s$$$ 的前 $$$i$$$ 个字符组成的子串，用 $$$\operatorname{suffix}(s, i)$$$ 表示由 $$$s$$$ 的后 $$$i$$$ 个字符组成的子串。
在此基础上，我们定义字符串 $$$s$$$ 的 $$$\operatorname{Porder}$$$ 值为满足以下条件的最大整数 $$$i$$$： $$$$$$\operatorname{prefix}(s, i) = (\operatorname{suffix}(s, i))^R$$$$$$其中 $$$0 \le i \le |s|$$$。特别地，若不存在正整数满足上述条件，则 $$$\operatorname{Porder}$$$ 值为 $$$0$$$。
字符串 $$$s$$$ 的子串定义为其从第 $$$l$$$ 个字符到第 $$$r$$$ 个字符的连续一段字符序列，其中下标从 $$$1$$$ 开始，满足 $$$1 \le l \le r \le |s|$$$。
现在，请你求出字符串 $$$s$$$ 的所有子串的 $$$\operatorname{Porder}$$$ 值之和。
输入仅一行，包含一个字符串 $$$s$$$ $$$(1 \le |s| \le 10^5)$$$，保证字符串中仅包含小写字母。
输出一行一个整数，表示 $$$s$$$ 的所有子串的 $$$\operatorname{Porder}$$$ 值之和。
aa
4
abcdba
9
以样例 2 为例：
- $$$\operatorname{Porder}$$$ 值为 $$$2$$$ 的子串有：$$$\texttt{abcdba}$$$（共 $$$1$$$ 个）。
- $$$\operatorname{Porder}$$$ 值为 $$$1$$$ 的子串有：$$$\texttt{bcdb}$$$，以及所有长度为 $$$1$$$ 的子串（共 $$$7$$$ 个）。
- 其余子串的 $$$\operatorname{Porder}$$$ 值均为 $$$0$$$。
因此，所有子串的 $$$\operatorname{Porder}$$$ 值之和为 $$$1 \times 2 + 7 \times 1 + 0 = 9$$$。
作为杀戮尖塔的最强角色，故障机器人拥有一个专属的机制——充能球。通过卡牌，故障机器人可以将生成的充能球放入充能球栏位中。在故障机器人的回合结束时，所有充能球会触发它们的被动效果；而在被消耗时，充能球也能产生爆发性的效果。
有一天，观者向故障机器人请教如何才能拥有极高的输出能力。于是，故障机器人向观者抛出了这样一个问题：
假设一局游戏共有 $$$n$$$ 个回合，而你有 $$$3$$$ 个初始为空的充能球栏位。在每个回合中，你有以下两种操作方式：
- 打出"电击"：每回合你有 $$$a_i$$$ 张"电击"。每次打出一张"电击"时，若当前存在空的充能球栏位，则占用一个空位并生成一个闪电充能球；否则直接造成 $$$d$$$ 点伤害。
- 打出"双重释放"：每回合你有 $$$b_i$$$ 张"双重释放"。每次打出一张"双重释放"时，若当前场上存在闪电充能球，则消耗一个闪电充能球并造成 $$$2d$$$ 点伤害，同时释放对应的栏位；否则无任何效果。
在每个回合内，你可以以任意顺序打出任意张"电击"和"双重释放"。回合结束时，若场上剩余 $$$x$$$ 个闪电充能球，则会额外造成 $$$x$$$ 点伤害，并且这些球会保留到下一回合，但手上剩余的"电击"和"双重释放"不会保留到下一回合。
作为杀戮尖塔第四弱的角色，观者无法解决这个问题，于是她向你求助，希望你能帮她计算出 $$$n$$$ 个回合内能造成的最大伤害。
第一行输入两个整数 $$$n, d$$$ $$$(1 \le n, d \le 10^5)$$$，分别表示游戏的总回合数以及触发直接伤害或消耗伤害时的数值 $$$d$$$。
接下来 $$$n$$$ 行，第 $$$i$$$ 行输入两个整数 $$$a_i, b_i$$$ $$$(0 \le a_i, b_i \le 10^5)$$$，分别表示在第 $$$i$$$ 个回合中"电击"和"双重释放"的数量。
输出一行一个整数，表示在 $$$n$$$ 个回合内能造成的最大伤害。
1 34 1
11
7 34 20 00 00 00 00 00 0
27
以第二个样例为例：
在第一回合，先打出 $$$1$$$ 张"电击"，然后打出 $$$1$$$ 张"双重释放"消耗掉该球并造成 $$$6$$$ 点伤害。接着打出 $$$3$$$ 张"电击"获得 $$$3$$$ 个闪电充能球。在接下来的每个回合结束时，都会因为场上剩余 $$$3$$$ 个球而额外造成 $$$3$$$ 点伤害，共计 $$$27$$$ 点伤害。
某学校集训队有 $$$2$$$ 位教练，共有 $$$n$$$ 支队伍，编号为 $$$1 \sim n$$$。今年有 $$$m$$$ 场 CCPC 区域赛，每支队伍最多参加 $$$2$$$ 站 CCPC 区域赛（可能有队伍参加 $$$0$$$ 站 CCPC 区域赛）。
每个赛站都会给每支参赛队伍的教练发放小礼品。不过，如果在同一个赛站中有多支参赛队伍的教练是相同的，那么该赛站只会给这位教练发放一个小礼品。
现在，每支队伍已经确定好要参加哪些赛站了，但是 CCPC 系统中还没有录入每支队伍的教练。在 CCPC 系统中，每支队伍只能指定 $$$1$$$ 位教练，并且一旦录入便无法改动。
请你合理地安排每支队伍的教练，使得这 $$$2$$$ 位教练拿到的小礼品总数最多。
第一行输入两个整数 $$$n, m$$$ $$$(1 \le n, m \le 10^6)$$$，分别表示队伍数和赛站数。
接下来 $$$m$$$ 行，每行首先输入一个整数 $$$k$$$ $$$(0 \le k \le n)$$$，表示学校参加该赛站的队伍数；接下来输入 $$$k$$$ 个整数，表示参加该赛站的队伍编号，保证这 $$$k$$$ 个整数互不相同。
输出一行一个整数，表示两位教练能拿到的小礼品总数的最大值。
3 32 1 22 1 32 2 3
5
3 32 1 32 2 30
4
Arona 和 Plana 是好朋友，遇到什么事情都可以通过友好地协商解决。
一天上午，Arona 打开冰箱，发现冰箱里竟然只剩下一个草莓牛奶了！她认为 Plana 会抢她的牛奶，于是向 Plana 发起了决斗！决斗内容如下：
Arona 给定一个正整数 $$$n$$$，然后随机选取一个 $$$1, 2, \cdots, n$$$ 的排列 $$$a$$$。令 $$$L$$$ 表示满足 $$$\max\limits_{j=1}^i a_j = a_i$$$ 的正整数 $$$i$$$ 的数量，$$$R$$$ 表示满足 $$$\min\limits_{j=1}^i a_j = a_i$$$ 的正整数 $$$i$$$ 的数量。如果 $$$L \ge R$$$，则 Arona 赢，否则 Plana 赢。
Arona 很自信，觉得她自己能轻松获得胜利，为了防止她胜利的时候 Plana 抱怨不公平，她又选了一个正整数 $$$k \le n$$$，并且将自己的胜利条件改为了 $$$L \ge R + k$$$。
虽然 Plana 一点也不在乎草莓牛奶，但她知道 Arona 能赢的概率不太大。Plana 现在想要知道这个概率具体是多少。屏幕前的你能帮她求出来这个具体值吗？
假设 Arona 能胜利的概率为 $$$p$$$，你只需要求出 $$$p \times n!$$$ 对 $$$998244353$$$ 取模后的结果即可。
此题包含多组测试数据。
第一行输入一个正整数 $$$T$$$ $$$(1 \le T \le 10^3)$$$，表示测试数据组数。
接下来 $$$T$$$ 行，每行输入两个整数 $$$n, k$$$ $$$(1 \le k \le n \le 10^6)$$$，含义同题目描述。
保证所有测试数据中 $$$n$$$ 的总和不超过 $$$10^6$$$。
对于每组测试数据，输出一行一个整数，表示所求的答案对 $$$998244353$$$ 取模后的结果。
2 3 1 3 2
2 1
105 397 312468 13579876 19876 12349876 6789234567 1234567 234555234567 123456234567 12345
7878338345199045303782408107474021604653690172358465928130271340136329270679313091
对于第一组数据，$$$n = 3$$$ 时共有 $$$6$$$ 种排列：
- 数列 $$$[1, 2, 3]$$$：$$$L = 3, R = 1$$$。
- 数列 $$$[1, 3, 2]$$$：$$$L = 2, R = 1$$$。
- 数列 $$$[2, 1, 3]$$$：$$$L = 2, R = 2$$$。
- 数列 $$$[2, 3, 1]$$$：$$$L = 2, R = 2$$$。
- 数列 $$$[3, 1, 2]$$$：$$$L = 1, R = 2$$$。
- 数列 $$$[3, 2, 1]$$$：$$$L = 1, R = 3$$$。
因此，当 $$$n = 3, k = 1$$$ 时，有 $$$[1, 3, 2]$$$ 和 $$$[1, 2, 3]$$$ 满足 $$$L \ge R + 1$$$ 的要求；而当 $$$n = 3, k = 2$$$ 时，只有 $$$[1, 2, 3]$$$ 满足 $$$L \ge R + 2$$$ 的要求。
灭霸并不喜欢传统排序算法。
对于一个长度为 $$$m$$$ 的序列 $$$a_1, a_2, \dots, a_m$$$，定义一次"灭霸排序"操作如下：
- 如果当前序列已经严格递增，即满足 $$$a_1 \lt a_2 \lt \dots \lt a_m$$$，则算法立即结束。
- 否则，从当前序列的 $$$m$$$ 个位置中，等概率随机选择恰好 $$$\lfloor m / 2 \rfloor$$$ 个位置删除，保留其余元素的相对顺序，然后继续对剩余序列执行同样的过程。
注意，上述删除操作中的 $$$m$$$ 指的是当前序列长度，而不是初始长度。也就是说，若某一轮开始时当前还剩下 $$$m$$$ 个元素且序列尚未有序，那么这一轮就会随机删除其中的 $$$\lfloor m / 2 \rfloor$$$ 个元素。
现在，先等概率随机生成一个长度为 $$$N$$$ 的排列 $$$p_1, p_2, \dots, p_N$$$，然后对该排列执行灭霸排序。
设最终剩余元素个数为 $$$X$$$。你需要求出 $$$\mathbb{E}[X]$$$，并将答案对 $$$998244353$$$ 取模后输出。
输入仅一行一个整数 $$$N$$$ $$$(1 \le N \le 10^6)$$$，表示初始排列的长度。
输出一行一个整数，表示 $$$\mathbb{E}[X]$$$ 对 $$$998244353$$$ 取模后的结果。
更形式化地，若 $$$\mathbb{E}[X]$$$ 的最简分数表示为 $$$\dfrac{P}{Q}$$$，则你需要输出 $$$P \cdot Q^{-1} \bmod 998244353$$$，其中 $$$Q^{-1}$$$ 表示 $$$Q$$$ 在模 $$$998244353$$$ 意义下的乘法逆元。
可以证明，在本题数据范围内，上述逆元一定存在。
2
499122178
4
83187031
- "排列"指由 $$$1, 2, \dots, N$$$ 这 $$$N$$$ 个互不相同的整数组成的序列。
- 所有随机选择均指在所有合法方案中等概率进行。
- 删除元素后，剩余元素的相对顺序保持不变。
长度为 $$$2$$$ 的排列只有两种：
- $$$[1, 2]$$$，此时序列已经有序，最终剩余元素个数为 $$$2$$$。
- $$$[2, 1]$$$，此时序列无序，需要随机删除 $$$1$$$ 个元素。无论删除哪一个，剩余序列长度都为 $$$1$$$，且一定有序，因此最终剩余元素个数为 $$$1$$$。
所以 $$$\mathbb{E}[X] = \frac{2 + 1}{2} = \frac{3}{2}$$$。
模 $$$998244353$$$ 意义下，$$$\frac{3}{2} \equiv 3 \cdot 2^{-1} \equiv 499122178 \pmod{998244353}.$$$
Asrit 正在玩杀戮尖塔二。他只剩 $$$1$$$ 滴血了，怪物即将攻击他，但是他抽到的手牌全都是攻击牌。
Asrit 有 $$$n$$$ 张手牌和 $$$m$$$ 点能量。每张手牌包含两个信息：耗能和伤害。耗能只有 $$$3$$$ 种可能：1、2 或 X。具体规则如下：
- 若一张手牌耗能为 1，伤害为 $$$d$$$，则当剩余能量 $$$\ge 1$$$ 时可打出。打出后消耗 $$$1$$$ 点能量，造成 $$$d$$$ 点伤害。
- 若一张手牌耗能为 2，伤害为 $$$d$$$，则当剩余能量 $$$\ge 2$$$ 时可打出。打出后消耗 $$$2$$$ 点能量，造成 $$$d$$$ 点伤害。
- 若一张手牌耗能为 X，伤害为 $$$d$$$，则当剩余能量 $$$ \gt 0$$$ 时可打出。打出后消耗当前所有的剩余能量，每消耗 $$$1$$$ 点能量造成 $$$d$$$ 点伤害（即总伤害为 $$$d \times \text{消耗能量数}$$$）。
Asrit 的游戏没有被瓦库接管，他可以以任意顺序打出任意满足条件的牌，且打出过的牌不会继续在手牌中。
请你告诉 Asrit，他的手牌最高能够打出多少伤害，以便他判断是否将会回到塔底。
第一行输入两个整数 $$$n, m$$$ $$$(1 \le n \le 10^6, 1 \le m \le 2 \times 10^6)$$$，分别表示手牌数和初始能量数。
接下来 $$$n$$$ 行，每行输入一个字符 $$$op$$$ 和一个整数 $$$d$$$ $$$(op \in \{\texttt{1}, \texttt{2}, \texttt{X}\}, 1 \le d \le 10^{12})$$$，表示一张手牌的耗能类型和伤害。
输出一行一个整数，表示能打出的最高伤害。
5 51 61 61 132 122 13
38
5 31 61 61 92 21X 11
33