Uolevi aikoo ajaa autolla Syrjälästä Perälään. Matka on $n$ kilometrin pituinen ja matkalla on kilometrin välein huoltoasema. Uolevi voi pysähtyä tankkaamaan valitsemillaan huoltoasemilla. Lisäksi Uolevin tapana on juoda kahvi aina kun hän pysähtyy huoltoasemalle.

Asemalla $i$ bensa maksaa $a_i$ euroa/litra ja kahvi maksaa $b_i$ euroa. Tehtävänä on valita huoltoasemat niin, että matkan kokonaishinta on mahdollisimman pieni.

Huoltoasemat on numeroitu $0 \ldots n-1$. Asema $i$ on $i$ kilometrin päässä Syrjälästä. Uolevin auto kuluttaa bensaa litran kilometrillä. Aluksi Uolevin tankki on tyhjä, eli hänen on pakko pysähtyä huoltoasemalla $0$.

Syöte

Ensimmäisellä rivillä on luku $n$, matkan pituus. Sitten tulee $n$ riviä, joilla on luvut $a_i$ ja $b_i$.

Tuloste

Tulosta ensimmäiselle riville kaksi lukua: optimaalinen matkan hinta ja kuinka monella huoltoasemalla pysähdytään. Tulosta toiselle riville järjestyksessä ensimmäisestä viimeiseen ne huoltoasemat joilla pysähdytään ja kolmannelle riville paljonko bensaa tankataan niillä huoltoasemilla joille pysähdytään. Jos optimaalisia vastauksia on useita, tulosta mikä tahansa niistä.

Rajat

• $1 \le n \le 5 \cdot 10^5$
• $1 \le a_i, b_i \le 10^6$

Esimerkki

Syöte:

5
15 3
10 10
10 4
2 10
3 1

Tuloste:

61 3
0 2 3
2 1 2