At Adelaide Oval, someone's mixed the Port Power and Adelaide Crows fans together! They hate each other, and would rather be with supporters of their own team. Given a field of footy fans, you can make one of four operations:

• Move a fan ~1~ unit up, at the cost of ~U~ inconvenience.
• Move a fan ~1~ unit down, at the cost of ~D~ inconvenience.
• Move a fan ~1~ unit left, at the cost of ~L~ inconvenience.
• Move a fan ~1~ unit right, at the cost of ~R~ inconvenience.

With these operations, you want to move the Port and Crows fans, so that they can be segregated by a single, vertical or horizontal fence. What is the minimum total amount of inconvenience required to do this?

Input

The first line consists of an integer ~n~ ~(1 \leq n \leq 500)~, the number of footy fans on the field.

The next line consists of 4 integers, ~U~, ~D~, ~L~ and ~R~ ~(1 \leq U, D, L, R \leq 10^5)~, representing the cost of moving any fan, up, down, left and right, respectively.

The next ~n~ lines contain ~I~, ~x~, and ~y~, where ~I~ is the identity of the fan (Port or Crows) who is standing at ~x, y~ ~(1 \leq x, y \leq 10^9)~.

Output

Output the minimum cost required to move the fans, so that Port and Crows players can be separated by a horizontal or vertical line.

Clarifications

• Two fans can occupy the same square at once.
• However, the input won't have two fans in the same square.
• Two fans can move past each other, even if they support opposing teams.
• You are able to move fans outside of the question's bounds (for example, negative coordinates are OK).
• In this problem, moving to the right is +x, moving down is +y.

Example

Input 1

8
4 5 2 1
P 1 1
P 1 5
P 3 6
P 4 3
C 2 2
C 3 4
C 5 2
C 6 5

Output 1

5

The optimal cost to separate the Port and Crows fans can be achieved by:

• Moving fan E right ~2~ squares. ~1 + 1 = 2~ cost.
• Moving fan F right ~1~ square. ~1~ cost.
• Moving fan D left ~1~ square. ~2~ cost.

Overall, it takes a minimum of ~2 + 1 + 2 = 5~ cost to separate the fans.

Input 2

2
2 7 6 3
P 1 1
C 2 2

Output 2

0

The fans are already separated.

Input 3

6
2 3 2 5
P 1 1
P 4 3
P 5 5
C 2 4
C 4 5
C 5 2

Output 3

9