Dino’s Infinite Run

Dino is running on a 2D plane – starting at the origin. There are two kinds of obstacles placed on the plane:

• Cactus: A vertical line segment from \( (x,0) \) to \( (x,h_i) \). When Dino is walking (i.e. on the ground, at \( y=0 \)) he will collide with a cactus if he exactly reaches its \( x \) coordinate.
• Bird: A vertical line segment from \( (x,d_i) \) to \( (x,u_i) \). When Dino is jumping his \( y \) coordinate is determined by his jump trajectory.

Dino has two modes of movement:

1. Walking: He moves along the \( x \)-axis on the ground. At any moment his position is \( (x,0) \). However, if he reaches a cactus (i.e. an obstacle at \( x_0 \)) then he immediately collides and the game ends with score \( x_0 \).
2. Jumping: When on the ground, Dino can start a jump from any real \( x \)-coordinate. The jump parameters are two positive integers: \( d \) and \( h \). Once he jumps from \( x=s \), his flight trajectory is given by \[ f(x) = \begin{cases} \displaystyle \frac{h}{d}(x-s) & \text{for } x-s\in[0,d)\\[1mm] \displaystyle -\frac{h}{d}(x-s)+2h & \text{for } x-s\in [d,2d)\\ \end{cases} \] Thus he lands at \( x = s+2d \) (with \( y=0 \)). Note that it is legal to initiate a new jump at the exact moment of landing.

If during a jump Dino passes an obstacle – whether it is a bird or a cactus – such that at the obstacle's \( x \)-coordinate his \( y \) equals a point on the obstacle (including the endpoints), then the game immediately ends and his score is the \( x \)-coordinate of that collision.

The goal is to plan a sequence of actions (walking and jumps) to maximize the final score, which is defined as the \( x \)-coordinate of the point at which Dino collides with an obstacle. If Dino can avoid collision forever, his score is defined to be Infinity.

Input/Output requirement in brief: Given the jump parameters and the obstacles (birds and cacti), compute the maximum achievable score by Dino.

inputFormat

The input begins with a line containing four positive integers:

d h b c

where \( d \) and \( h \) are the jump parameters, \( b \) is the number of birds, and \( c \) is the number of cacti.

The next \( b \) lines each contain three numbers:

x d_i u_i

denoting a bird obstacle located at \( x \) with vertical segment spanning from \( y=d_i \) to \( y=u_i \) (inclusive).

The following \( c \) lines each contain two numbers:

x h_i

denoting a cactus obstacle located at \( x \) with vertical segment from \( y=0 \) to \( y=h_i \) (inclusive).

outputFormat

Output the maximum score (i.e. the maximum \( x \)-coordinate Dino can reach before colliding), or output Infinity if Dino can avoid all obstacles indefinitely.

sample

2 6 1 1
3 4 5
5 3

5