Plus or Times

Interview

Time limit1sMemory limit2048 MB

Summary

Given a starting value P and N rounds where each round offers either adding c or multiplying by c, find the maximum final value.

Level: Medium5 of 10
Topics: Dynamic programming, Implementation
Solved: No attempts yet

Problem

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

+ c ( $-1000 \le c \le 1000$ ) adds $c$ to his current points.

x c ( $-2 \le c \le 2$ ) multiplies his current points by $c$ .

Adrian wants to maximize his points at the end of the game. Find the maximum points Adrian can have after completing all $N$ rounds.

Input

The first line contains two integers $N$ and $P$ ( $1 \le N \le 50$ , $-1000 \le P \le 1000$ ). Each of the next $N$ lines contains the two options of one round, separated by a space. Each option has the form T c, where $T$ is + or x. If $T$ is +, then $-1000 \le c \le 1000$ . If $T$ is x, then $-2 \le c \le 2$ .

Output

Print the maximum points Adrian can achieve as an integer on a single line.

Examples2

Example 1

Input

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

Expected output

Example 2
Input
```
3 123
+ 100 x 2
+ -100 x -2
x 0 x 0
```
Expected output
```
0
```