#P2304E. Puteng Puteng Bird

Puteng Puteng Bird

说明

Puteng Puteng Bird 是一款风靡一时的休闲手机游戏。玩家需要不断控制点击手机屏幕的频率来调节小鸟的飞行高度,让小鸟顺利通过画面右方的管道缝隙。

可是小菜并不想让小鸟那么顺利地通过管道的缝隙,因此他对每个管道缝隙施加了魔法,使得每个缝隙处产生防御盾,对小鸟产生干扰,阻碍小鸟的通过。

然而飞扬的小鸟具有十分特殊的技能,它拥有着特殊的攻击技能,能通过一定的运算来改变它受到的干扰。

小菜的魔法由 nn 道屏障组成,每道屏障由一个运算符 Temp\mathtt{Temp} 和防御值 TT 组成,其中运算符一定位运算是 OR\mathtt{OR}XOR\mathtt{XOR}AND\mathtt{AND} 中的一种,而防御值是一个非负整数 TT

假设小鸟还未通过屏障时攻击值为 XX,则当小鸟通过这道屏障后他的攻击值将变为 XTempTX \mathtt{Temp} T,最终小菜的屏障受损程度为小鸟原始的攻击值 XX 依次经过所有的屏障后得到的攻击值。

由于小鸟终究只是一只菜鸟,因此它的初始攻击值范围只能在 [0,M][0,M] 之间(一定是整数,攻击值可以为区间内的任意值,攻击值在通过屏障后不受到M的限制)。飞扬的小鸟对小菜恨得咬牙切齿,因此它希望通过选择一个合适的原始攻击值使它的攻击能让小菜的屏障受到最大的伤害,因此他希望你帮它计算一下,它的一次攻击最多能使小菜的屏障受到多少的伤害。

image

输入格式

第一行包含两个整数,依次为 n,mn,m,表示小菜有 nn 道屏障,飞扬的小鸟的初始攻击值的最大取值范围 MM

接下来 nn 行,依次表示每一道屏障的具体信息。每行包括一个字符串 Temp\mathtt{Temp} 和一个非负整数 TT

输出格式

一行一个整数,表示飞扬的小鸟的一次攻击最多使小菜的屏障产生多少损坏。

样例

样例输入1

3 8
OR 2
AND 5
XOR 8

样例输出1

13

提示

1n1051 \leq n \leq 10^5

0m1090 \leq m \leq 10^9

0T1090 \leq T \leq 10^9