Levi Ackerman. - Home | Facebook

Levi wants to defeat Beast Titan but he is too far away from him and the titan is throwing huge boulders over his teammates. He wants to reach the Beast Titan in T minutes. He is at a distance of D meters from him. He wants to reach the titan using his ODM gear which is powered by gas. To his surprise he saw that there are M Gas cylinders seperated by certain distances on his way.

He can use these cylinders and refill his ODM gear fully if his gear runs out of fuel.

Levi is an Ackerman so he has two modes:
1) Normal mode : In this mode he can cover a distance of 1 mile in 2 minutes which takes up 1 Kg of gas.
2) God mode : In this mode he can cover a distance of 1 mile in 1 minute, but it takes up 2 kg of gas.

Initially, at the starting point he has N different kinds of ODM gears each of which has a weight W and gas capacity C in kgs.

Levi is confused which ODM gear to choose and has very less time to make a decision so he asked you to help him.

Help Levi by choosing a gear with minimum weight so that he can reach the Beast Titan within time T and take him down.

NOTE: The titan and the cylinders all lie in straight line.

Input:
The first line contains positive integers N( number of ODM gears ), M (number of cylinders on the way), D (the distance between Levi and Titan) and T ( the time in which he wants to reach the titan).

Each of the next N lines contains two positive integers Wi and Ci - denoting weight of the ith Gear and its capacity.

The next line contains M distinct integers a1, a2, a3, a4 ... aM - denoting the location or the distance of the ith cylinder(in miles) in randomn order.
Constraints:

1 ≤ N ≤ 2·10^5,
1 ≤ M ≤ 2·10^5
2 ≤ D ≤ 10^9,
1 ≤ T ≤ 2·10^9.

1 ≤ Wi, Ci ≤ 10^9

1 ≤ ai ≤ D - 1

Output:

Print the minimum weight of the chosen ODM gear. If no such gear is present print -1.