피라미드 기단 2

새 피라미드를 세울 터 가운데 예산으로 감당할 수 있는 가장 큰 터를 찾으려 한다. 부지 조사 결과는 $M \times N$ 크기의 정사각형 칸 격자로 정리되어 있다. 피라미드의 기단은 격자의 변과 평행한 정사각형이어야 한다.

조사에서 장애물 $P$개를 찾았다. 각 장애물은 격자의 변과 평행한 직사각형이고, 서로 겹칠 수 있다. 피라미드를 세우려면 기단이 덮는 칸에서 장애물을 모두 없애야 한다. $i$번 장애물을 치우는 비용은 $C_i$다. 장애물은 통째로만 치울 수 있고, 일부만 치우는 것은 불가능하다. 한 장애물을 치워도 그것과 겹친 다른 장애물은 그대로 남는다.

부지의 크기 $M$과 $N$, 장애물 $P$개의 위치와 제거 비용, 예산 $B$가 주어질 때, 제거 비용의 합이 $B$를 넘지 않으면서 만들 수 있는 기단 한 변의 최대 길이를 구하는 프로그램을 작성하시오.

첫째 줄에 $M$과 $N$이 공백 하나로 구분되어 주어진다. ($1 \le M, N \le 10^6$)

둘째 줄에 예산 $B$가 주어진다. ($0 < B \le 2 \times 10^9$)

셋째 줄에 장애물의 개수 $P$가 주어진다. ($1 \le P \le 30000$)

다음 $P$개의 줄에 장애물의 정보가 한 줄에 하나씩 주어진다. 이 가운데 $i$번째 줄은 $i$번 장애물을 나타내고, 다섯 정수 $X_{i1}$, $Y_{i1}$, $X_{i2}$, $Y_{i2}$, $C_i$가 공백 하나로 구분되어 주어진다. 앞의 두 값은 장애물에서 가장 아래쪽 가장 왼쪽 칸의 좌표, 그다음 두 값은 가장 위쪽 가장 오른쪽 칸의 좌표, 마지막 값은 그 장애물을 치우는 비용이다. 격자에서 가장 아래쪽 가장 왼쪽 칸의 좌표는 $(1, 1)$이고, 가장 위쪽 가장 오른쪽 칸의 좌표는 $(M, N)$이다. ($1 \le X_{i1} \le X_{i2} \le M$, $1 \le Y_{i1} \le Y_{i2} \le N$, $1 \le C_i \le 7000$)

첫째 줄에 만들 수 있는 기단 한 변의 최대 길이를 정수 하나로 출력한다. 피라미드를 전혀 세울 수 없으면 $0$을 출력한다.

그림은 한 변의 길이가 $4$인 기단을 놓을 수 있는 두 위치를 보여준다.