Основа піраміди#278
Вас попросили знайти розмір найбільшої з можливих ділянок для будівництва нової піраміди. Для цього вам надано план ділянки, поділений на сітку з M \times N квадратних клітин. Основа піраміди повинна бути квадратом зі сторонами, паралельними до сітки.
На плані — прямокутних перешкод, паралельних до сторін сітки, які можуть перекриватися. Щоб побудувати піраміду, всі клітини, вкриті основою, мають бути очищені від перешкод.
Видалення -ї перешкоди коштує C_i. Перешкоду потрібно видалити повністю; часткове видалення неможливе. Видалення однієї перешкоди не впливає на інші.
Напишіть програму, яка за , описом перешкод , вартістю видалення кожної та бюджетом знаходить найбільшу сторону квадрата основи піраміди, щоб сумарна вартість очищення не перевищувала .
Програму перевірятимуть на трьох окремих наборах тестів. Для всіх справджуються обмеження:
Програма читає вхід у такому форматі:
- Рядок : два цілих числа (1 \leq M, N \leq 1\ 000\ 000) — розміри сітки. - Рядок : ціле число , ваш бюджет. - Рядок : ціле число , кількість перешкод. - Далі рядків: X_{i1}\ Y_{i1}\ X_{i2}\ Y_{i2}\ C_i (1 \leq X_{i1} \leq X_{i2} \leq M, 1 \leq Y_{i1} \leq Y_{i2} \leq N) — координати лівої нижньої та правої верхньої клітини перешкоди і вартість видалення.
Ліва нижня клітина сітки — , права верхня — (M, N).
Виведіть одне ціле число — максимальну можливу сторону основи піраміди. Якщо побудувати неможливо, виведіть .
Приклад 1