피라미드 밑면

새로 지을 피라미드의 밑면을 놓을 자리 중에서 가장 넓은 자리를 찾으려고 한다. 측량 결과 부지는 정사각형 칸으로 이루어진 가로 $M$ 열, 세로 $N$ 행의 격자로 나뉘어 있다. 피라미드의 밑면은 정사각형이고, 각 변은 격자의 변과 평행해야 한다.

측량에서는 서로 겹칠 수도 있는 장애물 $P$개를 찾았다. 장애물은 모두 격자의 변과 평행한 직사각형이다. 피라미드를 지으려면 밑면이 덮는 칸에 장애물이 하나도 남아 있으면 안 된다. $i$번 장애물을 치우는 비용은 $C_i$이고, 치울 때는 반드시 전체를 한 번에 치워야 한다. 장애물의 일부만 치울 수는 없다. 어떤 장애물을 치워도 그것과 겹쳐 있는 다른 장애물은 그대로 남는다.

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

첫째 줄에 $M$과 $N$이 공백 한 칸을 사이에 두고 주어진다. ($1 \le M, N \le 1\,000\,000$)

둘째 줄에 예산 $B$가 주어진다. 이 문제에서 $B$는 항상 $0$이다.

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

다음 $P$개 줄에는 장애물이 한 개씩 주어진다. 그중 $i$번째 줄에는 정수 다섯 개 $X_{i1}$, $Y_{i1}$, $X_{i2}$, $Y_{i2}$, $C_i$가 공백 한 칸씩을 사이에 두고 주어진다. 앞의 네 수는 $i$번 장애물에서 가장 아래쪽 가장 왼쪽 칸의 좌표와 가장 위쪽 가장 오른쪽 칸의 좌표이고, $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 7\,000$)

첫째 줄에 만들 수 있는 피라미드 밑면의 한 변의 최대 길이를 출력한다. 피라미드를 전혀 지을 수 없으면 $0$을 출력한다.

그림은 예제의 배치를 나타낸다. 한 변의 길이가 $3$인 밑면을 놓을 수 있는 자리는 그림에 표시된 한 곳뿐이다.