Cütlüklərə
Fermer Con, inəklərin bir-birinə mənəvi dəstək verdikdə sağılmasının daha asan olduğunu kəşf etdi. Buna görə də, o, m sayda inəyi (m ≤ 10^9, m cüt) m / 2 cütə bölmək istəyir. Hər cütü ayrı bir tövləyə yerləşdirir və bütün cütlər eyni vaxtda sağılır.
Hər inək fərqli miqdarda süd verir. Əgər bir cütdəki inəklər müvafiq olaraq a və b litr süd verirsə, bu cütü sağmaq üçün a + b vahid vaxt tələb olunur.
Con-a inəkləri ən yaxşı şəkildə cütləşdirərək, bütün sağım prosesinin minimal vaxtını müəyyən etməyə kömək edin.
Giriş Məlumatları
Birinci sətir n (1 ≤ n ≤ 10^5) ədədini ehtiva edir. Növbəti n sətirin hər biri x və y tam ədədlərini ehtiva edir, bu da Con-un y (1 ≤ y ≤ 10^9) litr süd istehsalı ilə x inəyinin olduğunu göstərir. Bütün x-lərin cəmi m - ümumi inək sayıdır.
Çıxış Məlumatları
İnəklərin optimal şəkildə cütləşdirildiyini nəzərə alaraq, bütün inəklərin sağılması üçün tələb olunan minimal vaxtı göstərin.
İzah
Məsələn, əgər 8 və 2 məhsuldarlığı olan inəkləri, həmçinin 5 və 5 məhsuldarlığı olan inəkləri cütləşdirsək, hər iki cütü sağmaq üçün hər cüt üçün 10 vahid vaxt sərf ediləcək. Bütün cütlərin sağılması paralel olaraq getdiyi üçün bütün proses 10 vahid vaxtda tamamlanacaq. Hər hansı digər cütləşmə daha çox vaxt tələb edəcək.