VZLA2019K - Koala Fan

no tags 

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 bi and pi 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


hide comments
Vipul Srivastava: 2019-11-23 20:23:33

Last edit: 2019-11-23 20:42:23

Added by:Samuel Nacache
Date:2019-10-27
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Genesis Kufatty - Used for Venezuelan 2019 ICPC Local Contest