Plus or Times

시간 제한1초메모리 제한2048 MB

요약

N개의 라운드마다 주어진 두 연산(+c 또는 xc) 중 하나를 현재 점수에 적용하며, 마지막 점수를 최대로 만든다.

난이도: 보통10점 중 5점
유형: 동적 계획법, 완전 탐색
정답자: 아직 제출이 없습니다

문제

Adrian is playing a game. When the game starts, Adrian will be given $P$ points as his initial points. The game consists of $N$ rounds, numbered from $1$ to $N$ . During round $i$ , Adrian has two options. Each option can be one of the following types:

+ $c$ ( $-1000 ≤ c ≤ 1000$ ) which will add his current points by $c$ , or
x $c$ ( $-2 ≤ c ≤ 2$ ) which will multiply his current points by $c$ .

Adrian wants to maximize his points at the end of the game. Help Adrian to determine the maximum points he can achieve after completing all $N$ rounds!

입력

Input begins with two integers $N$ $P$ ( $1 ≤ N ≤ 50$ ; $-1000 ≤ P ≤ 1000$ ) representing the number of rounds and the initial points during the game, respectively. Each of the next $N$ lines contains the two options in each round separated by a space. Each option is given in the format $T$ $c$ ( $T ∈ \\{$ +, x $\\}$ ; $-1000 ≤ c ≤ 1000$ if $T =$ +, or $-2 ≤ c ≤ 2$ if $T =$ x).

출력

Output an integer in a single line representing the maximum points Adrian can achieve at the end of the game.

예제2

예제 1

입력

3 123
+ 100 x 2
+ -100 x -2
+ 0 + 0

예상 출력

예제 2
입력
```
3 123
+ 100 x 2
+ -100 x -2
x 0 x 0
```
예상 출력
```
0
```