Maximizing the Ship's Final Displacement

A luxury cruise ship (which is really just a small wooden boat) can execute 4 types of commands:

• right X: rotates the ship clockwise by \(X\) degrees, where \(1\le X\le719\).
• left X: rotates the ship counterclockwise by \(X\) degrees, where \(1\le X\le719\).
• forward X: moves the ship forward (in its current facing direction) by \(X\) units, where \(1\le X\le1000\).
• backward X: moves the ship backward (i.e. in the opposite direction of its current facing) by \(X\) units, where \(1\le X\le1000\).

Someone has written down n commands in arbitrary order. Your task is to find an ordering of these commands so that the ship’s final distance from the starting point is maximized.

How to maximize the displacement?

The ship starts facing east (we take this as \(0^\circ\)). Notice that if movement commands (i.e. forward and backward) are executed while the ship has the same facing, then their effects add linearly. However, if all commands are executed in the original order without rotation adjustments, a forward moves east and a backward moves west, and they subtract.

You are allowed to reorder all commands but must execute each exactly once. By strategically placing the turning commands (right and left) between movement commands you can control the orientation when a movement is executed.

Ideally, you want:

1. All forward commands to be executed when the ship is facing east \((0^\circ)\).
2. All backward commands to be executed when the ship is facing west. Since a backward move is in the opposite direction of the ship's current facing, you want the ship to face \(180^\circ\) so that it moves east as well.

Thus, if you can use a subset of the turning commands to achieve a net rotation of \(180^\circ\) (modulo \(360^\circ\)) before executing the backward commands, then all movements will add up. In that case the final displacement will be

[ \text{displacement} = \text{(sum of all forward distances)} + \text{(sum of all backward distances)}. ]

If it is impossible to select turning commands whose rotation sums to \(180^\circ\) (modulo \(360^\circ\)), then you cannot reorient the backward moves to add to the displacement. In this case, the best you can do is to execute all movement commands in a row (with no turning in between) so that both forward and backward are performed with the initial facing. The final displacement then is

[ \text{displacement} = \left| \text{(sum of forward distances)} - \text{(sum of backward distances)} \right|. ]

Your program should determine and output the maximum possible displacement.

inputFormat

The first line contains an integer n (the number of commands).

Each of the next n lines contains a command of the form:

• right X
• left X
• forward X
• backward X

It is guaranteed that for turning commands, \(1 \le X \le 719\) and for movement commands, \(1 \le X \le 1000\).

outputFormat

Output a single integer, the maximum possible distance from the starting point that can be achieved by some reordering of the commands.

sample

4
forward 10
backward 5
right 180
left 360

15