注意

[2024-10-16 0:15] 制約の変更を行いました。詳しくは制約をご覧ください。

問題文

変数 $x$ についての数式 $f(x)$ があり、$Q$ 個のシンボル（オペランドまたは演算子）からなる列 $S = (s_1, s_2, \cdots, s_Q)$ として与えられます。

$S$ は逆ポーランド記法で記述されており、次の手順で計算することで $f(x)$ の値を得ることができます。

はじめ、空の数列 $A$ があります。

次の操作を $i = 1, 2, \cdots, Q$ の順番で行います。ここで、各操作の直前の $A$ を、長さ $n$ の数列 $(A_1, A_2, \cdots, A_n)$ とします。

• $s_i$ がオペランド（整数または X ）のとき、以下の操作を行う。
  • 整数のとき、$A$ を長さ $n + 1$ の数列 $(A_1, A_2, \cdots, A_n, \bm{s_i})$ に更新する。
  • X のとき、 $A$ を長さ $n + 1$ の数列 $(A_1, A_2, \cdots, A_n, \bm{x})$ に更新する。


• $s_i$ が演算子（ +, min, max のいずれか）のとき、以下の操作を行う。 このとき、$n \ge 2$ であることが保証される。
  • + のとき、 $A$ を長さ $n - 1$ の数列 $(A_1, A_2, \cdots, A_{n-2}, \bm{A_{n-1} + A_n})$ に更新する。
  • min のとき、 $A$ を長さ $n - 1$ の数列 $(A_1, A_2, \cdots, A_{n-2}, \bm{\min\{A_{n-1}, A_n\}})$ に更新する。
  • max のとき、 $A$ を長さ $n - 1$ の数列 $(A_1, A_2, \cdots, A_{n-2}, \bm{\max\{A_{n-1}, A_n\}})$ に更新する。

全ての操作が完了した後、$A$ は長さ $1$ の数列になることが保証されます。このときの $A_1$ が計算結果となります。

このとき、$f(x) = Y$ を満たす非負整数 $x$ のうち最小のものを求めてください。ただし、そのような $x$ が存在しない場合、-1 を出力してください。

制約

• $Q, Y$ は整数である。
• $1 \le Q \le 2 \times 10^5$
• $0 \le Y \le \color{red}{\sout{\textcolor{black}{10^{14}}}} ~ \color{red}{10^{13}}$ （変更日時：2024-10-16 0:15）
• $s_i$ はオペランド（整数または X ） または演算子（ +, min, max のいずれか）である。
• $s_i$ が整数ならば、$0 \le s_i \le 10^9$
• 問題文の手順で計算するときに矛盾が生じるような入力は与えられない。

入力

入力は以下の形式で標準入力から与えられる。

$Q$ $Y$
$s_1$ $s_2$ $\ldots$ $s_Q$

出力

$f(x) = Y$ を満たす非負整数 $x$ のうち最小のものを出力せよ。ただし、そのような $x$ が存在しない場合、-1 を出力せよ。

サンプル

3 5
X 2 +

3

7 9
X X 3 max + 11 min

-1

11 10
X X X X X + + + + 10 max

0