Beksweet

Batas Waktu	1 detik
Batas Memori	32 MB
Pak Dengklek sedang bersenang hati, ia membagi permen-permen kepada N (1 ≤ N ≤ 100.000) ekor bebeknya. Sungguh baiknya, Pak Dengklek mengantarkan permen-permen tersebut langsung ke kandang bebek-bebeknya. Lucunya, Pak Dengklek tidak membagi sama rata permen-permen tersebut. Ada bebek yang mendapatkan banyak, ada pula yang mendapatkan sedikit (bahkan ada yang tidak mendapatkannya). Mengetahui hal ini, para bebek yang ternyata sangat setia kawan berencana melakukan penyama-rataan. Tentunya dalam rangka penyama-rataan ini, beberapa permen perlu dipindahkan dari seekor bebek kepada bebek yang lainnya.

Kandang bebek-bebek dapat diasumsikan berada pada satu garis lurus dan posisinya diwakilkan oleh sebuah bilangan bulat P yang merupakan jarak kandang tersebut terhadap titik acuan (titik 0) dalam satuan meter. Masing-masing bebek memiliki kandangnya sendiri-sendiri dan tidak ada dua kandang yang berada di titik yang sama. Untuk memindahkan permen-permen tersebut, para bebek yang malas keluar kandang meminta bantuan para ayam yang ternyata memang hobi jalan-jalan. Sayangnya, nothing is for free. Untuk pengantaran permen dengan jarak X, ayam meminta bayaran sebanyak X permen. Singkat kata, jika ayam diminta memindahkan Y permen dari kandang pada posisi A ke kandang pada posisi B hanya Y-(abs(A-B)) buah permen yang akan tiba di kandang pada posisi B. Tentunya permen yang pecah tidaklah enak, oleh karena itu setiap pemindahan permen selalu melibatkan jumlah permen yang merupakan bilangan bulat.

Kini, tugas Anda adalah untuk membantu para bebek mengatur pemindahan permen-permen tersebut sedemikian sehingga setiap bebek memiliki setidaknya M buah permen, dan M itu adalah bilangan bulat terbesar yang mungkin (semakin banyak permen yang didapatkan, semakin senang pula para bebek).

Format Masukan

Baris pertama berisi sebuah bilangan bulat N yang merupakan jumlah bebek Pak Dengklek. N baris berikutnya berisi dua buah bilangan bulat P dan S (0 ≤ P, S ≤ 10^12), posisi kandang bebek yang bersangkutan dan banyaknya permen yang mula-mula diberikan kepada bebek tersebut.

Format Keluaran

Sebuah bilangan bulat M yang merupakan jumlah permen terbesar yang dapat dimiliki masing-masing bebek (setiap bebek memiliki permen sebanyak itu atau lebih).

Contoh Masukan 1

3
1 0
2 21
4 0
Contoh Keluaran 1

6
Contoh Masukan 2

4
20 300
40 400
340 700
360 600
Contoh Keluaran 2

415
Contoh Masukan 3

3
1200 20
15 100
5 70
Contoh Keluaran 3

20
Penjelasan

Pada contoh pertama, 7 buah permen dikirim dari kandang pada posisi 2 ke kandang pada posisi 1, 8 buah permen dikirim dari kandang pada posisi 2 ke kandang pada posisi 4. Pada akhirnya, semua bebek mendapatkan tepat 6 buah permen. Tidak ada cara lain sehingga semua bebek dapat memiliki setidaknya 7 permen atau lebih.