# Target Firing

Difficulty : Medium

Community success rate: 38%

Approved by an anonymous CodinGamer VirtualAtom ludowsky

A higher resolution is required to access the IDE

- 242

## Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

## Statement

## Goal

**«Story»**

Your spaceship is under attack by aliens! (It's actually your friend's spaceship, so the situation is even worse) Luckily your spaceship is equipped with an antimatter beam, while the aliens only have cheap (but still dangerous) laser pointers. Can you destroy all alien spaceships safely, or should you flee?

**«Prompt»**

As the AI within the ship's computer, your goal is to

**determine the optimal order of alien spaceships to destroy**such that you leave the encounter with the maximum strength of your shields.

**Print the remaining strength of the shields**, or

**more damage than your shields**can handle. Your friend will not forgive you if the ship is damaged.

**«Details»**

The encounter can be modeled by turn-based combat. Your spaceship's shields begin with

`N`alien spaceships of various properties. These properties are:

`SHIP`- the type of the spaceship, which can be either

`HP`- the amount of damage the spaceship can receive before being destroyed,

`ARMOR`- the damage reduction of the spaceship, and

`DAMAGE`- the amount of damage the spaceship deals per turn.

On each turn, all alien spaceships reduce your ship's shields by

`DAMAGE`as your antimatter beam charges, and then one spaceship takes damage from your antimatter beam. Your beam deals

`ARMOR`. Luckily, your antimatter beam does double damage to

`ARMOR`. Your antimatter beam always deals

**at least**

`ARMOR`is greater than your beam's damage.

Input

**Line 1:**An integer

`N`for the number of alien spaceships.

**Next**One string followed by three integers, space-separated, representing the

`N`lines:`SHIP`type,

`HP`,

`ARMOR`, and

`DAMAGE`of the alien spaceship.

Output

An integer representing the maximum strength of shields left after an optimal encounter, or FLEE if your spaceship will take hull damage (shield strength < 0).

Constraints

2 ≤

1 ≤

0 ≤

FIGHTER or CRUISER

`N`≤ 501 ≤

`HP`,`DAMAGE`< 10000 ≤

`ARMOR`< 50`SHIP`=Example

Input

2 FIGHTER 10 0 500 FIGHTER 10 0 800

Output

3200

A higher resolution is required to access the IDE