Description

You are the owner of a cake chain that sells three different flavors of cake: strawberry, chocolate, and honey. Each branch sells exactly one flavor of cake and provides free delivery service.

Today, N customers have ordered cakes, and there are N branches located at different positions along the same road. Due to a shortage of delivery staff, each branch has only one employee available to make deliveries.

Each customer can purchase exactly one cake, and each branch must deliver its cake to exactly one customer. Cakes of different flavors cannot be delivered to the wrong customer. In other words, the flavor ordered by a customer must be the same as the flavor sold by the branch delivering the cake.

Your task is to determine which customer each branch should deliver its cake to so that the total delivery distance is minimized.

All branches and customers are located on the same road, so their positions can be represented by integer coordinates. The delivery distance between a branch and a customer is the absolute difference between their positions.

The three cake flavors are represented by the following letters:

• S: Strawberry
• C: Chocolate
• H: Honey

For example, suppose there are 3 branches and 3 customers:

3 S 5 C 10 H 15 S 13 C 11 H 19

The first N lines represent the branches, while the next N lines represent the customers. Therefore:

Branches:

S 5 C 10 H 15

Customers:

S 13 C 11 H 19

Since cakes of different flavors cannot be delivered to the wrong customers, the branches must be matched with customers of the same flavor:

S 5  → S 13   distance = 8 C 10 → C 11   distance = 1 H 15 → H 19   distance = 4

Therefore, the minimum total delivery distance is:

8 + 1 + 4 = 13

 

Your program MAY use C/C++ standard library headers.

Input

The first line contains an integer N, representing the number of branches and the number of customers.
The next 2N lines contain the branch and customer information. Each line contains a character T and an integer P:

T P

For the first N lines, T represents the flavor sold by a branch, and P represents the branch's position on the road.
For the next N lines, T represents the flavor ordered by a customer, and P represents the customer's position on the road.

T is guaranteed to be one of: S C H

You are guaranteed that the following conditions hold:

• 1 <= N < 10^6
• 0 <= P < 2^64
• The minimum possible total delivery distance is less than 2^64
• For each flavor, the number of branches selling that flavor is equal to the number of customers ordering it.

Output

Output a single integer representing the minimum total delivery distance required to deliver all cakes while satisfying the flavor restrictions. The output must end with \n.

Sample Input  Download

Sample Output  Download

Tags

Discuss