Piramidanın əsası#278
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 M \times N ö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.
Plan üzrə şəbəkənin tərəflərinə paralel olan düzbucaqlı maneələr var. 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.
-ci maneənin aradan qaldırılması C_i dəyərinə başa gəlir. Maneə tamamilə aradan qaldırılmalıdır; yalnız bir hissəsi aradan qaldırıla bilməz. Bir maneənin aradan qaldırılması digərinə təsir etmir.
Verilən və , maneənin təsviri, hər birinin aradan qaldırılma dəyəri və büdcə verilirsə, maneələrin aradan qaldırılmasının ümumi dəyəri -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.
Proqramınız üç bir-birini kəsmə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:
Proqram aşağıdakı formatda məlumat oxumalıdır:
- Sətir : İki tam ədəd və (1 \leq M, N \leq 1\ 000\ 000), şəbəkənin ölçüləri. - Sətir : Tam ədəd , sizin büdcəniz. - Sətir : Tam ədəd , maneələrin sayı. - Növbəti sətirin hər biri: 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), maneənin sol alt və sağ üst hüceyrəsinin koordinatları və aradan qaldırılma dəyəri.
Şəbəkənin sol alt hüceyrəsi , sağ üst hüceyrəsi (M, N) koordinatlarına malikdir.
Tək bir tam ədəd çap edin: 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ə, çap edin.
Nümunə 1