VZLA2019K - Koala Fan
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
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 |