피라미드 밑면

새로운 피라미드를 지을, 예산 안에서 가능한 가장 큰 부지를 찾으려고 합니다. 결정을 돕기 위해 측량 자료가 주어지는데, 부지는 $M \times N$ 크기의 정사각형 칸 격자로 나뉜어져 있습니다. 피라미드의 밑면은 격자의 변과 평행한 변을 갖는 정사각형이어야 합니다.

측량으로 서로 겹칠 수 있는 $P$개의 장애물이 확인되었습니다. 각 장애물은 격자의 변과 평행한 변을 갖는 직사각형입니다. 피라미드를 지으려면 밑면이 덮는 모든 칸에서 장애물을 제거해야 합니다. $i$번째 장애물을 제거하는 비용은 $C_i$이며, 장애물은 반드시 통째로 제거해야 합니다(일부만 제거할 수는 없습니다). 또한 어떤 장애물을 제거해도 그와 겹치는 다른 장애물에는 아무런 영향을 주지 않습니다.

측량 격자의 크기 $M$, $N$, $P$개의 장애물 정보, 각 장애물의 제거 비용, 그리고 예산 $B$가 주어질 때, 제거 비용의 합이 $B$를 넘지 않도록 하면서 만들 수 있는 피라미드 밑면의 최대 한 변 길이를 구하는 프로그램을 작성하세요.

입력은 표준 입력으로 주어집니다.

• 첫째 줄: 공백으로 구분된 두 정수 $M$과 $N$. ($1 \le M, N \le 10^{6}$)
• 둘째 줄: 사용할 수 있는 최대 비용(예산) $B$. ($B = 0$)
• 셋째 줄: 측량에서 발견된 장애물의 개수 $P$. ($1 \le P \le 1000$)
• 다음 $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$을 출력합니다.

위 그림은 한 변의 길이가 $3$인 밑면을 놓을 수 있는 유일한 위치를 보여 줍니다.