## 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 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 POutput:93 10 10

Input:

5 5 D

5 5 D

10 11 P10

Output:

### 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 |