Robot Bullet-Dodging Simulation

You are given a rectangular game board in the first quadrant with coordinates from ( (0,0) ) to ( (n,m) ). A robot is initially located at ( (0,0) ). You are also given an original command string ( C' ) consisting of digits (each digit from 0 to 4) and a repetition constant ( k ). The final command string ( C ) is obtained by concatenating ( C' ) exactly ( k ) times. The robot executes the commands in ( C ) one per second. If the robot has no command defined at a given second, it remains stationary. The commands are described as follows:

[ \begin{array}{|c|l|}\hline \textsf{\textbf{Command}} & \textsf{\textbf{Description}} \ \hline \mathbf{0} & \textsf{Robot stays in place} \ \hline \mathbf{1} & \textsf{Robot moves left 1 unit: from ((x,y)) to ((x-1,y))} \ \hline \mathbf{2} & \textsf{Robot moves down 1 unit: from ((x,y)) to ((x,y-1))} \ \hline \mathbf{3} & \textsf{Robot moves up 1 unit: from ((x,y)) to ((x,y+1))} \ \hline \mathbf{4} & \textsf{Robot moves right 1 unit: from ((x,y)) to ((x+1,y))} \ \hline \end{array} ]

Each command in the original string ( C' ) incurs a cost. In particular, if ( C' ) contains the command digit ( i ) then it costs ( P_i ) (given as input) per occurrence.

The game lasts for ( d ) seconds. During the game, there are ( b ) bullets. Each bullet is represented by a 6-tuple ( (l_i, r_i, x_i, y_i, p_i, q_i) ) with the following meaning:

• The bullet is generated at second ( l_i ) at position ( (x_i, y_i) ).
• The bullet is destroyed at second ( r_i ) (after collision detection at that second).
• In every second the bullet is active (i.e. for seconds ( c ) with ( l_i < c \le r_i )), it moves by ( p_i ) units in the ( x )-direction and ( q_i ) units in the ( y )-direction.

Each second is divided into five stages in the following order:

1. Robot Movement Stage: At second ( c ), the robot executes the ( c\text{-th} ) command of ( C ) (if it exists, otherwise it stays in place).
2. Bullet Movement Stage: For every bullet that is already generated (i.e. for which ( l_i < c \le r_i )), update its position. In particular, for a bullet ( (l_i, r_i, x_i, y_i, p_i, q_i) ) the position at the beginning of second ( c ) is defined as ( P=(x_i+(c-1-l_i)p_i,; y_i+(c-1-l_i)q_i) ) and after movement it becomes ( Q=(x_i+(c-l_i)p_i,; y_i+(c-l_i)q_i) ).
3. Bullet Generation Stage: For any bullet with ( l_i = c ), generate it at position ( (x_i,y_i) ). (For these newly generated bullets, set ( P=Q=(x_i,y_i) ).)
4. Collision Detection Stage: The robot explodes if either:
   • Its position is outside the board (i.e. not in ( [0,n] \times [0,m] )).
   • It is hit by any bullet. A bullet hits the robot if the robot’s position lies on the line segment connecting ( P ) and ( Q ) (endpoints inclusive).
5. Bullet Destruction Stage: Any bullet with ( r_i = c ) is destroyed.

If the robot explodes at any point during the ( d ) seconds, the game is considered a failure and you should output GAME OVER. Otherwise, if the robot survives through the end of second ( d ), the game is a victory, and you must output the total cost of the original command string. The cost is computed as ( k ) multiplied by the sum of the costs of each command in ( C' ).

Note on Collision Detection: For a bullet that was generated before the current second (i.e. ( c > l_i )), the bullet moves from ( P=(x_i+(c-1-l_i)p_i,; y_i+(c-1-l_i)q_i) ) to ( Q=(x_i+(c-l_i)p_i,; y_i+(c-l_i)q_i) ). If the robot’s position ( R=(r_x,r_y) ) lies on the segment ( \overline{PQ} ) (including endpoints), the robot is hit. For bullets generated in the current second (i.e. ( l_i = c )), since ( P=Q ), the robot is hit if ( R=P ).

Your task is to simulate the game given the input and output the total cost if the robot survives all ( d ) seconds, or output GAME OVER if the robot explodes.

inputFormat

The input is given in the following format:

 n m k d
 C' 
 P0 P1 P2 P3 P4
 b
 l1 r1 x1 y1 p1 q1
 l2 r2 x2 y2 p2 q2
 ...
 lb rb xb yb pb qb

Where:

• n and m specify the board dimensions (the board spans from (0,0) to (n,m)).
• k is the number of times the original command string C' is repeated.
• d is the total number of seconds for the game.
• C' is a string of digits (each from 0 to 4) representing the original command sequence.
• P0, P1, P2, P3, P4 are the costs for commands 0, 1, 2, 3, and 4 respectively.
• b is the number of bullets.
• Each of the following b lines contains six integers: l r x y p q, representing a bullet as described above.

outputFormat

Output a single line containing the total cost of the command string if the robot survives (i.e. the game is a victory), or GAME OVER if the robot explodes at any point during the game.

sample

5 5 1 3
0
1 2 3 4 5
0

1