/* -*- coding: utf-8 -*- * * 2927.cc: No.2927 Reverse Polish Equation - yukicoder */ #include #include #include using namespace std; /* constant */ const int MAX_QN = 200000; enum { X = -1, ADD = -2, MIN = -3, MAX = -4 }; /* typedef */ using ll = long long; /* global variables */ int fs[MAX_QN]; ll as[MAX_QN]; /* subroutines */ ll calc(int qn, ll x) { int n = 0; ll a0, a1; for (int i = 0; i < qn; i++) { switch (fs[i]) { case X: as[n++] = x; break; case ADD: a0 = as[--n], a1 = as[--n]; as[n++] = a0 + a1; break; case MIN: a0 = as[--n], a1 = as[--n]; as[n++] = min(a0, a1); break; case MAX: a0 = as[--n], a1 = as[--n]; as[n++] = max(a0, a1); break; default: as[n++] = fs[i]; break; } } return as[0]; } /* main */ int main() { int qn; ll y; scanf("%d%lld", &qn, &y); for (int i = 0; i < qn; i++) { char s[16]; scanf("%s", s); fs[i] = (s[0] == 'X') ? X : (s[0] == '+') ? ADD : (s[1] == 'i') ? MIN : (s[1] == 'a') ? MAX : atoi(s); } ll x0 = -1, x1 = y + 1; while (x0 + 1 < x1) { ll x = (x0 + x1) / 2; if (calc(qn, x) >= y) x1 = x; else x0 = x; } if (calc(qn, x1) != y) puts("-1"); else printf("%llu\n", x1); return 0; }