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