더하기 또는 곱하기

면접 대비

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

요약

시작 값 P와 N개의 라운드가 주어집니다. 각 라운드에서 c를 더하거나 c를 곱하는 두 선택지 중 하나를 골라 얻을 수 있는 최댓값을 구합니다.

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

문제

아드리안이 게임을 하고 있다. 게임이 시작되면 아드리안은 초기 점수로 $P$ 점을 받는다. 게임은 1번부터 $N$ 번까지 번호가 매겨진 $N$ 개의 라운드로 이루어진다. $i$ 번째 라운드에서 아드리안은 두 가지 선택지 중 하나를 고를 수 있다. 선택지는 다음 두 종류 중 하나이다.

+ c ( $-1000 \le c \le 1000$ )는 현재 점수에 $c$ 를 더한다.

x c ( $-2 \le c \le 2$ )는 현재 점수에 $c$ 를 곱한다.

아드리안은 게임이 끝났을 때의 점수를 최대로 만들고자 한다. 모든 $N$ 개의 라운드를 마친 뒤 아드리안이 얻을 수 있는 최대 점수를 구하라.

입력

첫 줄에 두 정수 $N$ 과 $P$ 가 주어진다 ( $1 \le N \le 50$ , $-1000 \le P \le 1000$ ). 이어지는 $N$ 개의 줄에는 각 라운드의 두 선택지가 공백으로 구분되어 주어진다. 각 선택지는 T c 형식이며, $T$ 는 + 또는 x이다. $T$ 가 +이면 $-1000 \le c \le 1000$ 이고, $T$ 가 x이면 $-2 \le c \le 2$ 이다.

출력

아드리안이 얻을 수 있는 최대 점수를 정수로 한 줄에 출력한다.

예제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
```