Efficient Shoe Selection

Sarah is preparing for a running event, and she must choose a pair of running shoes that not only costs as little as possible but also meets the timing requirement of finishing her run. The route is divided by several checkpoints. For each segment between the start, checkpoints, and the finish, Sarah can choose one of two running strategies: a fast run with time cost given by \(\lfloor\frac{d}{2}\rfloor \times 4 + (d \bmod 2)\times 6\) minutes, or a normal run with time cost \(d \times 6\) minutes, where \(d\) is the distance of the segment in kilometers.

For each pair of running shoes, the energy limit denotes the maximum distance in kilometers the pair can handle for each segment. If the distance for any segment exceeds the shoe's energy limit, that pair cannot be used for the run.

Your task is to help Sarah select the most economical pair of shoes (i.e. with the minimum price) such that she can complete the entire route within the target time \(t\) minutes. If no such pair exists, output \(-1\).

The input format provides:

• \(p\): the number of available pairs of running shoes.
• \(m\): the number of checkpoints on the path.
• \(d\): the total distance of the path in kilometers.
• \(t\): the maximum allowed time in minutes.
• \(p\) lines (each containing two integers): the price and the energy limit for each pair of shoes.
• \(m\) lines (each containing one integer): the position (in kilometers) of each checkpoint along the path.

inputFormat

The input is provided via standard input (stdin) in the following format:

 p m d t
 price_1 energy_1
 price_2 energy_2
 ...
 price_p energy_p
 checkpoint_1
 checkpoint_2
 ...
 checkpoint_m

Where \(p, m, d, t\) are integers and the following lines provide the shoe information and checkpoint positions, respectively.

outputFormat

Output a single integer to standard output (stdout) representing the minimum price of a pair of shoes that enables Sarah to complete the run within \(t\) minutes. If no such pair exists, output \(-1\).

## sample

3 2 10 40
15 20
10 18
12 25
3
6

10