== include(page="template/taskheader" task_id="bursa") ==

Gigi are un pont la bursa. El stie pentru fiecare din urmatoarele $N$ zile care va fi pretul $P[i]$ al unei actiuni la compania X. Stiind ca a reusit sa stranga suma de bani $S$ ( de pe la rude si prieteni ), afisati profitul maxim pe care il poate obtine Gigi si o modalitate de a-l obtine. Presupuneti ca Gigi poate cumpara in fiecare zi oricate actiuni doreste cu conditia sa ii ajunga banii pe care ii are. De asemenea, puteti presupune ca Gigi poate vinde in orice zi, oricate actiuni doreste, dintre cele pe care le detine. Transferul de bani / actiuni se realizeaza instantaneu.

Gigi are un pont la bursa. El stie pentru fiecare din urmatoarele $N$ zile care va fi pretul $P[i]$ al unei actiuni la compania X. Stiind ca a reusit sa stranga suma de bani $S$ (de pe la rude si prieteni), afisati profitul maxim pe care il poate obtine Gigi. Presupuneti ca Gigi poate cumpara in fiecare zi oricate actiuni doreste, cu conditia sa ii ajunga banii pe care ii are. De asemenea, puteti presupune ca Gigi poate vinde in orice zi, oricate actiuni doreste, dintre cele pe care le detine. Transferul de bani / actiuni se realizeaza instantaneu.

h2. Date de intrare

h2. Date de ieşire

Fişierul de ieşire $bursa.out$ va contine pe prima linie profitul maxim pe care il poate obtine Gigi. Urmatoarele $N$ linii vor contine fiecare cate $2$ numere: $A[i]$, reprezentand numarul de actiuni pe care le vinde Gigi in ziua $i$, si $B[i]$, reprezentand numarul de actiuni pe care le cumpara Gigi in ziua $i$.

Fişierul de ieşire $bursa.out$ va contine pe prima linie profitul maxim pe care il poate obtine Gigi.

h2. Restricţii

* $1 ≤ N ≤ 1 000 000$

* $1 ≤ N ≤ 100 000$

* $1 ≤ S ≤ 10 000 000 000$

* $1 ≤ P[i] ≤ 100 000 000$

* $1 ≤ P[i] ≤ 500 000$
* Se garanteaza ca suma de bani detinuta de Gigi se va incadra pe un intreg cu $64$ de biti, la orice moment de timp

h2. Exemplu

| 3 100
  7 1 12
| 1100

  0 0
  0 100
  100 0

|
h3. Explicaţie

7245