Andy is a really cute person and he wants to buy a koala. There are n available koalas, for each koala its beauty and cost are known. There are two accepted types of money in the world: donuts and polygons, so each koala cost can be either in donuts or polygons. Due the bad relations between The Linear States and Exponenzula no money changes between the types are allowed.
Help Andy to find two different koalas with the maximum total beauty so that he can buy both at the same time.

Input

The first line contains three integers n, d and p the number of koalas, the number of donuts and polygons Andy has.

The next n lines describe koalas. Each of these lines contain two integers b_i and p_i the beauty and the cost of the i-th koala, and then a letter "D" or "P", describing in which type of money is the cost of koala i: in donuts or in polygons, respectively.

Output

Print the maximum total beauty of exactly two koalas Andy can buy. If he can't buy two koalas, print "sad:(".

Example

Input:
3 7 6
10 8 D
4 3 D
5 6 P
Output:
9

Input:
3 10 10
5 5 D
5 5 D
10 11 P

Output:
10

Constraints

• 2 ≤ n ≤ 100000

• 0 ≤ d, p ≤ 100000

• 1 ≤ b i , p i ≤ 100000