Piramidanın əsası
Sizdən yeni bir piramida tikmək üçün mümkün olan ən böyük sahənin ölçüsünü tapmağınız xahiş olunur. Bunun üçün sizə mövcud sahənin planı təqdim olunur və bu plan MxN ölçülü kvadrat hüceyrələrdən ibarət bir şəbəkəyə bölünmüşdür. Piramidanın əsası, şəbəkənin tərəflərinə paralel olan kvadrat şəklində olmalıdır.
Plana görə, şəbəkənin tərəflərinə paralel olan düzbucaqlı maneələrdən ibarət P maneə toplusu göstərilib. Bu düzbucaqlı maneələr bir-birinin üzərinə düşə bilər. Piramida tikmək üçün onun əsası ilə örtülən bütün hüceyrələr maneələrdən təmizlənməlidir.
i-ci maneənin aradan qaldırılması C_i dəyərinə başa gəlir. Maneə aradan qaldırıldıqda, tamamilə aradan qaldırılır, yəni maneənin yalnız bir hissəsini aradan qaldıra bilməzsiniz.
Qeyd etmək lazımdır ki, bir maneənin aradan qaldırılması onunla üst-üstə düşən digər maneələrə təsir etmir.
Şəbəkənin ölçüləri M və N, P maneələrin təsviri, hər birinin aradan qaldırılma dəyəri və mövcud büdcə B verildikdə, maneələrin aradan qaldırılmasının ümumi dəyəri B-ni aşmayan ən böyük piramida əsası üçün mümkün olan ən böyük tərəf uzunluğunu tapan proqram yazın.
Məhdudiyyətlər
Proqramınız üç kəsişməyən test dəsti ilə qiymətləndiriləcək. Onların hamısı üçün aşağıdakı məhdudiyyətlər yerinə yetirilir:
- 1 <= M, N <= 1 000 000 (M, N – şəbəkənin ölçüləri) - 1 <= C_i <= 7 000 (C_i – i-ci maneənin aradan qaldırılma dəyəri) - 1 <= X_i1 <= X_i2 <= M (X_i1 və X_i2 – i-ci maneənin ən sol və ən sağ hüceyrəsinin X-koordinatları) - 1 <= Y_i1 <= Y_i2 <= N (Y_i1 və Y_i2 – i-ci maneənin ən aşağı və ən yuxarı hüceyrəsinin Y-koordinatları)
Giriş verilənləri
Proqramınız standart girişdən aşağıdakı formatda məlumat oxumalıdır:
- 1-ci sətir: Bir boşluqla ayrılmış iki tam ədəd – M və N. - 2-ci sətir: B tam ədədi – sizin büdcəniz. - 3-cü sətir: Planda olan maneələrin sayını göstərən P tam ədədi. - Növbəti P sətirin hər biri bir maneəni təsvir edir: bu sətirlərdən i-ci i-ci maneəni təsvir edir. Hər bir sətir bir boşluqla ayrılmış 5 tam ədəddən ibarətdir: müvafiq olaraq maneənin sol alt hüceyrəsinin koordinatlarını, maneənin sağ üst hüceyrəsinin koordinatlarını və maneənin aradan qaldırılma dəyərini təyin edən X_i1, Y_i1, X_i2, Y_i2 və C_i.
Şəbəkənin sol alt hüceyrəsi (1, 1) koordinatlarına, sağ üst hüceyrəsi isə (M, N) koordinatlarına malikdir.
Çıxış verilənləri
Proqramınız standart çıxışa bir tam ədəd ehtiva edən tək bir sətir çıxarmalıdır – tikilə biləcək piramida əsası üçün mümkün olan ən böyük tərəf uzunluğu. Əgər piramida tikmək mümkün deyilsə, proqramınız 0 ədədini çıxarmalıdır.