🐧🐧 Bob the penguin 🐧🐧 has had enough 🐧. In rage, he throws his homework at you >:(

🐧 the penguin has ~K~ presents, where each present has its own weight ~w_i~ and height ~h_i~. 🐧 puts each of these presents into his two types of processing machines; weight and height. However, since 🐧's been too lazy to fix his machine, each weight processor can only process weights ~\leq weight[i]~, and each height processor can only process heights ~\leq height[i]~. Furthermore, each processor can only process a single present every second, and each present only needs to be processed once. 🐧 wants to know one thing: what is the least number of seconds required to process every present?

However, 🐧, being greatly unhappy with you, decides to make your life even more annoying. He provides you with ~L~ shrinkifiers, each allowing you to shrink the height of a present by one. Shrinkifiers are able to shrink the same present multiple times, and you do not need to use all ~L~ shrinkifiers. Can you solve this problem?

Input Specification

The first line of input will contain three space-separated integers ~N, M, K, L~.

The second line of input will contain ~N~ space-separated integers ~weight[i]~, representing the weight capacity of the ~i^{th}~ weight processor.

The third line of input will contain ~M~ space-separated integers ~height[i]~, representing the height capacity of the ~i^{th}~ height processor.

The next ~K~ lines of input will contain two space-separated integers ~w_i, h_i~, representing the weight and height specifications of the ~i^{th}~ present.

Output Specification

Output ~1~ line, containing a single integer repersenting the least number of seconds required to process every present. If it is never achievable, output -1

Constraints

For all subtasks,

~1 \leq weight[i], height[i], w_i, h_i \leq 10^7~

Marks Allocated	Bounds on ~N~	Bounds on ~M~	Bounds on ~K~	Bounds on ~L~
~4\%~	~N = 1~	~M = 0~	~K = 1~	~L = 0~
~13\%~	~1 \leq N \leq 10^5~	~M = 0~	~1 \leq K \leq 10^6~	~L = 0~
~33\%~	~1 \leq N \leq 10^5~	~1 \leq M \leq 10^5~	~1 \leq K \leq 10^6~	~L = 0~
~50\%~	~1 \leq N \leq 10^5~	~1 \leq M \leq 10^5~	~1 \leq K \leq 10^6~	~0 \leq L \leq K~

Sample Input 1

1 2 5 0
10000
1 3
1 1
2 3
2 5
5 4
3 4

Sample Output 1

3

Sample Explanation 1

Notice that the last ~3~ presents all can only be processed by the singular weight procecssor. Therefore, it takes at least ~3~ seconds to process all of them. We have no shrinkifiers to modify the heights.

Sample Input 2

1 1 1 1
1
100
10 101

Sample Output 2

1

Sample Explanation 2

We use the shrinkifier on the only present in order to be able to process it.