$$ \newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor} \newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil} \renewcommand{\mod}{\,\mathrm{mod}\,} \renewcommand{\div}{\,\mathrm{div}\,} \newcommand{\metar}{\,\mathrm{m}} \newcommand{\cm}{\,\mathrm{cm}} \newcommand{\dm}{\,\mathrm{dm}} \newcommand{\litar}{\,\mathrm{l}} \newcommand{\km}{\,\mathrm{km}} \newcommand{\s}{\,\mathrm{s}} \newcommand{\h}{\,\mathrm{h}} \newcommand{\minut}{\,\mathrm{min}} \newcommand{\kmh}{\,\mathrm{\frac{km}{h}}} \newcommand{\ms}{\,\mathrm{\frac{m}{s}}} \newcommand{\mss}{\,\mathrm{\frac{m}{s^2}}} \newcommand{\mmin}{\,\mathrm{\frac{m}{min}}} \newcommand{\smin}{\,\mathrm{\frac{s}{min}}} $$

Prijavi problem


Obeleži sve kategorije koje odgovaraju problemu

Još detalja - opišite nam problem


Uspešno ste prijavili problem!
Status problema i sve dodatne informacije možete pratiti klikom na link.
Nažalost nismo trenutno u mogućnosti da obradimo vaš zahtev.
Molimo vas da pokušate kasnije.

Пуно фигурица

vreme memorija ulaz izlaz
0,2 s 64 Mb standardni izlaz standardni ulaz

Овај задатак је поновљен у циљу увежбавања различитих техника решавања.

Друштвену игру игра \(k\) играча и сваки играч игру почиње са по \(k\) фигура, при чему све фигуре једног играча морају бити исте јачине, док су јачине фигура различитих играча различите. Фигуре су доступне у неограниченим количинама, при чему је познат низ јачина доступних фигура. Напиши програм који одређује највећи број играча \(k\) који могу играти игру тако да разлика између укупне јачине свих фигура било која два играча не пређе задату границу.

Улаз

Са стандардног улаза се учитава број \(n\) (\(1 \leq n \leq 10^5)\), а затим у наредном реду \(n\) различитих расположивих јачина фигура (природни бројеви између \(1\) и \(10^5\)). Наредни ред садржи границу (природни број између \(1\) и \(10^{12}\)).

Излаз

На стандардни излаз исписати два броја раздвојена размаком – број \(k\) и најмању разлику укупних јачина фигура када игра \(k\) играча.

Пример

Улаз

5 5 4 2 7 3 15

Излаз

4 12

Објашњење

Ако играчи узму по четири фигуре јачине \(5\), \(4\), \(2\) и \(3\) највећа разлика јачина фигура играча биће \(4\cdot 5 - 4\cdot 2 = 12\). Ако би играло \(5\) играча, морали би да узму и фигуре јачине \(7\) и највећа разлика би била \(5\cdot 7 - 5\cdot 2 = 25\), што је веће од дозвољене границе.

Morate biti ulogovani kako biste poslali zadatak na evaluaciju.