Getting-Up Syndrome

In the 21st century, many people have caught an odd disorder called getting-up syndrome. Its symptoms are having great difficulty getting out of bed in the morning and still feeling out of sorts after getting up. ATM, a generally high-spirited teenager, has been struggling with getting-up syndrome. Through extensive research, he found the cause. On the vast seabeds of the Pacific Ocean lives a giant dragon named DRD who holds the essence of sleep itself and can extend everyone's sleeping time at will. With DRD's every movement, getting-up syndrome worsens for everyone, growing at a frightening rate and affecting more and more people in the world. To put an end to this terrible malady, ATM has decided to travel to the seabed of the Pacific and slay this evil dragon once and for all.

After untold hardships, ATM has finally reached DRD's resting place. He now braces for the arduous battle ahead. DRD has a very special tactic. His line of defense transforms the attack power of the opponent through a series of calculations to minimize the damage done to himself. Roughly speaking, DRD's line of defense consists of n defense gates. Each gate contains an operator op and a parameter t. The operator is guaranteed to be one of OR, XOR, or AND, and the parameter is guaranteed to be a nonnegative integer. If one's power before going through a defense gate is x, then the power after going through it is x op t. Finally, the damage done to DRD equals his opponent's initial striking power x after it has been through all n defense gates.

Since ATM's skill is limited, the initial attack power of his strike can only be an integer between 0 and m (he may pick any of 0, 1, …, m as his initial attack power), but the final attack power after passing through the gates is not bounded by m. To conserve energy, he has to pick the optimal initial power with which to attack to maximize the damage done to DRD. Help him calculate how much damage he can do to DRD with one strike.

The first line contains two integers n and m, indicating that DRD uses n defense gates and that ATM can pick any integer between 0 and m as his initial striking power.

The next n lines each describe a single defense gate. Each line consists of a string of characters representing op, followed by a space, followed by a nonnegative integer t representing the parameter of that gate.​​​​​​​

Output one line containing a single integer, the maximum damage ATM can do to DRD with one strike.

• 2 ≤ n ≤ 105
• 2 ≤ m ≤ 109
• 0 ≤ t ≤ 109 
• op is one of OR, XOR, AND