M. Obstacle Course
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Bessie is running through an obstacle course! There are $$$N$$$ platforms, initially at height $$$h_i$$$ ($$$h_i$$$ is even so they will cross at an integer time). Each platform moves either up or down one meter per second. To jump from a platform of height $$$x$$$ to a platform of height $$$y$$$, it takes Bessie $$$\lvert x-y \rvert$$$ energy and $$$0$$$ time. Bessie can also wait at any platform.

Bessie wants to move through the course with minimal energy. Find the minimum energy that must be expended for Bessie to complete the course (travel from the first platform to the last platform).

Input

First line contains $$$N (N \leq 10^5)$$$.

Next $$$N$$$ lines contain $$$1$$$ integer and $$$1$$$ uppercase letter each line: $$$h_i (\lvert h_i \rvert \leq 10^9), h_i$$$ is always even and a letter c denoting whether the platform is moving up or down where U denotes up and D denotes down.

—

Tests in subtasks are numbered from $$$1-20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.

Tests $$$1-2$$$ satisfy that $$$N \leq 20$$$.

Tests $$$3-6$$$ satisfy that $$$N \leq 1000$$$.

Tests $$$7-8$$$ satisfy that all platforms move in the same direction.

Tests $$$9-20$$$ satisfy no additional constraints.

Output

Output one line, the minimum energy to go through the course.

Example
Input
5
36 U
14 D
0 D
16 U
14 D
Output
54