Problem Description

You must have seen these blood-pressure-rising game ads on social media or short-video apps: the player controls a character with a pitiful combat power value. Facing two doors labeled “$\times 10$” and “$\div 2$”, the player still walks to “$\div 2$” without hesitation, and in the end gets mercilessly defeated by a high-level monster.

Every time you see such a video, you want to jump into the screen and play for them. Now, you have finally downloaded this game called “Formula Warriors”, and you decide to play it yourself, break the stupid operations in the ads, and show everyone what a true strongest warrior looks like.

Initially, the warrior you control has combat power equal to a positive integer $x$.

The game has $n$ levels. In each level, there are $2$ doors in front of the warrior, and the warrior must and can only choose one door to pass through.

Each door has a formula on it. When the warrior passes through the door, the warrior’s combat power $x$ becomes:

$$x \leftarrow \lfloor\text{Expression1} \ \ \text{Operator} \ \ \text{Expression2}\rfloor$$

Where:

• $\text{Operator}$ is one of the four operators: add ($+$), subtract ($-$), multiply ($\times$), divide ($\div$).
• In $\text{Expression1}$ and $\text{Expression2}$, exactly one is the warrior’s current combat power $x$, and exactly one is the given positive integer constant $v$ on the door.
• $\lfloor A \rfloor$ means taking the floor of $A$.

It is guaranteed that no matter what legal choices you make in the game, after completing the $i$-th operation ($1\le i\le n$), the warrior’s current combat power $x$ always satisfies $1\le x\le 10^{18}$.

You need to plan these $n$ choices properly so that after passing all $n$ levels, the final combat power $x$ is maximized. Output the maximum possible combat power.

Input Format

This problem contains multiple test cases. The first line of input contains a positive integer $T$ ($1\le T\le 10^3$), representing the number of test cases.

Next are descriptions of $T$ test cases.

The first line of each test case contains two positive integers $n$ and $x$ ($1\le n\le 10^4$, $1\le x\le 10^{18}$), separated by a space, representing the number of levels and the warrior’s initial combat power.

The next $n$ lines describe the formulas on the $2$ doors of level $i$. Each line contains $6$ space-separated elements: the first $3$ elements describe the first door, and the last $3$ elements describe the second door.

For each door, the given $3$ elements strictly follow the format $\text{Expression1} \ \ \text{Operator} \ \ \text{Expression2}$, where:

• $\text{Operator}$ is one of the characters $\texttt{+}$, $\texttt{-}$, $\texttt{*}$, $\texttt{/}$, representing addition, subtraction, multiplication, and division.
• In $\text{Expression1}$ and $\text{Expression2}$, exactly one is the character $\texttt{x}$, representing the player’s current combat power; exactly one is a positive integer $v$ ($1\le v\le 10^{18}$), representing the constant given on the door.

For example, $\texttt{x + 5}$ means updating combat power to $\lfloor x + 5 \rfloor$; $\texttt{100 / x}$ means updating combat power to $\lfloor 100 \div x \rfloor$.

It is guaranteed that no matter what legal choices you make in the game, after completing the $i$-th operation ($1\le i\le n$), the warrior’s current combat power $x$ always satisfies $1\le x\le 10^{18}$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^4$.

Output Format

For each test case, output one line containing an integer, representing the maximum combat power the warrior can obtain after passing $n$ levels.

2
3 2
x + 3 x * 2
100 / x x * 10
x - 10 1000 / x
1 1145141919810
1145141919810 + x 3 * x

50
3435425759430

Hint

In sample test case 1, one optimal choice is: first door $\to$ first door $\to$ second door.

The corresponding combat power changes are: $2 \to 5 \to 20 \to 50$.

Translated by ChatGPT 5