Bajtocy jest szanowanym prezesem ogromnej korporacji, składającej się z N różnych filii. Firma ma nieskończone rezerwy finansowe w banku na jednej z oddalonych, egzotycznych wysp. Zbliża się koniec roku, Bajtocy musi więc przedstawić raport z działania spółki. Jest świadom, iż złe wyniki doprowadzą do utraty zaufania partnerów strategicznych, dlatego chciałby ustalić pewien poziom zysku, zwany dalej progiem, który powinien osiągnąć każdy dział. Według jego planu, gdy filia zarobi więcej niż wynosi próg zmuszona jest wysłać nadwyżkę do banku rezerw. Gdy zaś znajduje się "pod" progiem (tzn. jej zysk jest mniejszy niż założony), otrzymuje z banku brakującą różnicę.
Oczywiście chytry plan Bajtocego jest niezgodny z prawem panującym w Bajtoświecie, dlatego musi on ukryć każdą transakcję filii z bankiem. Do tego celu zmuszony jest wynająć armię agentów do transportowania pieniędzy w walizkach (przelew nie wchodzi bowiem w grę). Ci zaś każą sobie płacić K Bajtodolarów od każdego przeniesionego tysiąca Bajtodolarów. Bajtocy nienawidzi, jak ktoś naciąga jego firmę, dlatego podstawowym jego celem jest aby jak najmniej zapłacić agentom.
Sytuacja zaczyna przerastać Bajtocego. Zatrudnił Ciebie do wyznaczenia największego poziomu zysku, w taki sposób, aby kwota, którą zapłaci agentom była najmniejsza. Warto zauważyć, iż największy próg może być, w niektórych przypadkach, ujemny.
W pierwszej linii znajdują się dwie liczby całkowite: N (1 <= N <= 106) oraz K (1 <= K <= 106). W kolejnych N liniach znajdują się dwie liczby całkowite ai, bi (0 <= ai, bi <= 106), oznaczające kolejno dochód oraz poniesione koszty i-tej filii (w tysiącach Bajtodolarów).
W jedynej linii wyjścia wypisz dwie liczby całkowite: szukany poziom zysku każdej filii (w tysiącach Bajtodolarów) oraz kwotę, którą Bajtocy zapłaci agentom za pomoc (w Bajtodolarach).
3 10 10 7 1 3 9 4
3 70
Gdy zaproponujemy poziom zysku równy 3 to:
Filia pierwsza ma zysk na poziomie 3, czyli tyle ile wyniesie próg. Do banku nie wyśle więc nic.
Filia druga zanotowała stratę na poziomie 2, czyli będzie 5 tysięcy Bajtodolarów pod progiem. Bank zatem wyśle jej taką kwotę, a Bajtocy zapłaci agentom 5*10 = 50 Bajtodolarów.
Filia trzecia uzyskała zysk 5, czyli zmuszona będzie odesłać 2 tysiące do banku. Bajtocy zapłaci wówczas agentom 2*10=20 Bajtodolarów.
[Zgłoś rozwiązanie] [Moje zgłoszenia]