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