\includegraphics{https://static.e-olymp.com/content/e3/e390003da5a9fb3cf824dbf8a8e4480434029106.jpg} Вас попросили знайти розмір найбільшого з можливих місць для будівництва нової піраміди. Для того, щоб допомогти вам прийняти рішення, вам предоставлено план доступної ділянки, який для зручності поділено сіткою на \textbf{MxN} квадратних клітин. Основа піраміди повинна бути квадратом зі сторонами, паралельними сторонам сітки. На плані показано множину з \textbf{P} перешкод, які є прямокутниками зі сторонами, паралельними сторонам сітки. Прямокутники можуть перекриватись. Щоб побудувати піраміду, всі клітини, покриті її основою, повинні бути очищені від перешкод. Видалення \textbf{i}-ї перешкоди має вартість \textbf{C_i}. Всякий раз, коли перешкода видаляється, вона видалається повністю, тоьто, ви не можете видалити лише частину перешкоди. Слід відмітити, що видалення перешкоди не впливає на інші перешкоди, з якими вона перекривалась. Напишіть програму, яка за заданими розмірностями сітки \textbf{M} та \textbf{N}, опису \textbf{P} перешкод, вартості видалення кожної з них, а також наявному бюджету \textbf{B} знаходить максимальну довжину сторони найбільшого з можливих місць для основи піраміды, такого, що сумарна вартість видалення перешкод не перевищує \textbf{B}. \textbf{Обмеження} Ваша програма буде оцінена з використанням трьо неперетинаючихся наборів тестів. Для всіх них виконуються наступні обмеження: \textbf{1 <= M, N <= 1 000 000} (\textbf{M}, \textbf{N} -- розмірності решітки) \textbf{1 <= C_i <= 7 000} (\textbf{C_i} -- вартість видалення \textbf{i}-ї перешкоди) \textbf{1 <= X_i1 <= X_i2 <= M} (\textbf{X_i1} та \textbf{X_i2} -- \textbf{X}-координати самої лівої та самої правої клітини \textbf{i}-ї перешкоди, відповідно) \textbf{1 <= Y_i1 <= Y_i2 <= N} (\textbf{Y_i1} та \textbf{Y_i2} -- \textbf{Y}-координати самої нижньої та самої верхньої клітини \textbf{i}-ї перешкоди, відповідно) \InputFile Ваша програма повинна читати зі стандартного вводу дані у наступному форматі: • Рядок \textbf{1} містить два цілих числа, відокремлених одним пропуском -- \textbf{M} та \textbf{N}, відповідно. • Рядок \textbf{2} містить ціле число \textbf{B} -- ваш бюджет. • Рядок \textbf{3} містить ціле число \textbf{P} -- кількість перешкод, що є на плані. • Кожен з наступних \textbf{P} рядків описує перешкоду: \textbf{i}-ий з цих рядків описує \textbf{i}-у перешкоду. Кажен рядок складається з \textbf{5} цілих чисел: \textbf{X_i1}, \textbf{Y_i1}, \textbf{X_i2}, \textbf{Y_i2}, та \textbf{C_i}, відокремлених одним пропуском. Вони задають відповідно координати нижньої лівої клітини перешкоди, координати верхньої правої клітини перешкоди та вартість видалення перешкоди. Нижня ліва клітина решітки має координати (\textbf{1}, \textbf{1}), верхня права клітина решітки має координати (\textbf{M}, \textbf{N}). \OutputFile Ваша програма повинна вивести у стандартний вивід єдиний рядок, що містить одне ціле число -- максимально можливу довжину сторони основи піраміди, яку можна побудувати. Якщо піраміду побудувати не можна, ваша програма повинна вивести число \textbf{0}.