G. Sergio's Happiest Office
time limit per test
2.1 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Sergio runs an office with $$$m$$$ windows arranged in a row. Blind $$$j$$$ currently leaves an opening of $$$a_j$$$ centimeters and cannot be opened beyond $$$h_j$$$ centimeters.

Sergio's colleagues, Miguel and Racsó, convinced him that the team must get enough natural light: according to the wellness program, reasonable sun exposure helps maintain healthy vitamin D levels and improves the mood in the office. There are $$$n$$$ office workers in total.

Office worker $$$i$$$ receives light from all windows from $$$l_i$$$ to $$$r_i$$$, inclusive. Their light level is the sum of the openings of those blinds.

While Miguel and Racsó are at lunch, Sergio can only raise blinds. So that the change is not obvious, the building controller allows at most $$$k$$$ centimeters of total movement. He must choose non-negative integers $$$x_1, \ldots, x_m$$$ such that $$$$$$x_1 + x_2 + \cdots + x_m \leq k$$$$$$ and $$$$$$a_j + x_j \leq h_j$$$$$$ for each blind $$$j$$$. After the adjustment, the opening of blind $$$j$$$ will be $$$a_j + x_j$$$ centimeters. It is guaranteed that at least one adjustment satisfying all the constraints exists.

The management wants to maximize the light received by the least illuminated office worker. Print only that maximum value.

Input

The first line contains three integers $$$m$$$, $$$n$$$ and $$$k$$$ ($$$1 \leq m, n \leq 2 \times 10^{5}$$$, $$$0 \leq k \leq 10^{12}$$$).

The second line contains $$$m$$$ integers $$$a_1, \ldots, a_m$$$ ($$$0 \leq a_j \leq 10^{9}$$$).

The third line contains $$$m$$$ integers $$$h_1, \ldots, h_m$$$ ($$$a_j \leq h_j \leq 10^{9}$$$).

Each of the following $$$n$$$ lines contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \leq l_i \leq r_i \leq m$$$). Different office workers may have the same interval of windows.

Output

Print a single integer: the maximum possible value of the minimum illumination among all office workers.

Example
Input
4 3 5
1 0 2 1
3 2 2 4
1 2
2 3
4 4
Output
3
Note

Explanation for example 1

Sergio can raise the blinds by $$$0, 2, 0, 3$$$ centimeters. The light levels of the three office workers become $$$3, 4, 4$$$. Achieving at least $$$4$$$ for all of them would require three centimeters on the first two windows and three on the fourth, a total of six centimeters; Sergio only has five.