Ən yaxşı performans
ACME Inc. fabrikini yenidən təşkil edərək, faydasız xırda şeylərin istehsalını maksimuma çatdırmaq istəyir. Yeni fabrik dizaynı p müstəqil və eyni istehsal xətlərindən ibarətdir. Hər bir istehsal xəttinə müəyyən sayda işçi təyin edilə bilər.
İstehsal xətlərinin məhsuldarlığı, onlara təyin edilmiş işçilərin faktiki sayından asılı deyil, çünki bütün işlər maşınlar tərəfindən yerinə yetirilir. Lakin işçilər növbə ilə işlədikləri üçün və yerli təhlükəsizlik qaydalarına əsasən, istehsal xətti yalnız bütün işçilər mövcud olduqda aktiv ola bilər. Yəni, istehsal xəttinin məhsuldarlığı, həmin xəttə təyin edilmiş bütün işçilərin eyni vaxtda mövcud olduğu müddətə bərabərdir. Hər bir xəttin məhsuldarlığının müsbət olması vacibdir (sonuncu işçi ilk işçinin bu xətti tərk etməsindən əvvəl gəlməlidir), əks halda işçilər işlərinin mənasız olduğunu düşünəcəklər.
ACME, bəzi əmək qanunlarına görə işçilərdən heç birini işdən çıxara bilməz, yəni bütün n işçi hansısa istehsal xəttinə təyin edilməlidir. Bu, fabrikin ümumi məhsuldarlığını azalda bilər.
Bütün bu qaydalar və tənzimləmələr ACME idarəçiliyi üçün çətinlik yaradır. Onlara yeni zavodlarında mümkün olan maksimum ümumi məhsuldarlığı (istehsal xətləri p-nin ümumi məhsuldarlığını) müəyyən etməkdə kömək edə bilərsinizmi?
Giriş məlumatları
Aşağıdakılardan ibarətdir:
bir sətir iki ədəd n və p (1 ≤ p ≤ n ≤ 200) - işçilərin sayı və istehsal xətlərinin sayı;
n sətir, hər biri iki ədəd a və b (0 ≤ a < b ≤
10^5) ehtiva edir, bu da işçinin a vaxtında gəldiyini və b vaxtında getdiyini göstərir.
Məlumdur ki, işçilərin istehsal xətlərinə uyğun təyin edilməsi üçün ən azı bir uyğun təyinat mövcuddur.
Çıxış məlumatları
Fabrikanın maksimum məhsuldarlıq səviyyəsini çıxarın.