You have been given the dimensions M and N of the list, the description of the P rectangular plots, the cost of removing each of the plots, and the budget B you have.

You need to find the maximum possible side length of the base of the garden such that the total cost of removing residential plot does not exceed B.

Input Format

Input 1: It will be string which tells two integers separated by a single comma that represent M and N respectively.

Input 2: It will be the integer B, the maximum cost you can afford (i.e., your budget). It is the cost of removing ith plot.

Input 3: It will be the integer P, the residential plots found in the list.

Input 4: It will be string array where:

The first line of the array tells the total number of elements in the array i.e.

Each of the next P lines describes a residential plot. The ith of these lines describes the ith plot. Each line consists of 5 integers: Xi1, Yi1, Xi2, Yi2, and Ci separated by single comma. They represent respectively the coordinates of the bottommost, leftmost cell of the plot, the coordinates of the topmost & rightmost cell of the plot, and the cost of removing the plot. The bottommost, leftmost cell on the grid has coordinates (1, 1) and the topmost, rightmost cell has coordinates (M, N).

1 <= Xi1 <= Xi2 <= M, X coordinates of the leftmost and the rightmost cells of the ith residential plot

1 <= Yi1 <= Yi2 <= N, Y coordinates of the bottommost and the topmost cells of the ith residential plot

Constraints

1 <= M, N <= 1,000,000

1 <= Ci <= 7,000

0 <= B <= 1,00,000

1<= P <= 1,00,000

Output Format

It will be an integer that tells the maximum length of the base of the garden such that the total cost of removing plots does not exceed B.

Sample TestCase 1

Input

6,9

42

5

5

4,1,6,3,12

3,6,5,6,9

1,3,3,8,24

3,8,6,9,21

5,1,6,2,20

Output

4