E. Алаг цамхаг

хугацааны хязгаарлалт 1.5 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Бяцхан Жанет шоогоор тоглох дуртай. Шоо бүр өнгө $c_{i}$ болон хэмжээ $s_{i}$ гэсэн хоёр үзүүлэлттэй. Зөвхөн хоёр өнгийн шоонуудыг давхарлан тавьж босгосон цамхгийг алаг цамхаг гэнэ. Мөн алаг цамхгийн шоонуудын өнгө нь сөөлжилсөн байх ёстой. Өөрөөр хэлбэл зэргэлдээ хоёр шоо бүрийн өнгө өөр байна. Алаг цамхаг хамгийн багадаа хоёр шооноос бүрдэх ба үүнээс өөр ямар нэг хязгаарлалт байхгүй. Алаг цамхагийн жишээг доорх зурагт үзүүлэв.

Алаг цамхагийн өндөр нь цамхагийг бүрдүүж байгаа шоонуудын хэмжээний нийлбэр байна. Бяцхан Жанет байгаа өөрт байгаа шоонуудаа ашиглан хамгийн өндөр алаг цамхаг барихыг хүсэж байв. Түүнд тусална уу.

Оролт

Эхний мөрөнд шоонуудын тоог илэрхийлэх бүхэл тоо $n$ байна. ($2 ≤ n ≤ 10^{5}$)

Дараагийн $n$ мөрөнд мөр бүрд шооны тодорхойлолт байна. Шооны тодорхойлолт нь зайгаар тусгаарлагдсан $c_{i}$, $s_{i}$ ($1 ≤ c_{i}, s_{i} ≤ 10^{9}$) хоёр тоо байх бөгөөд эдгээр нь харгалзан $i$-р шооны өнгө болон хэмжээ.

Ялгаатай өнгөтэй хоёр шоо ямагт олдохоор оролтын өгөгдөл өгөгдөнө.

Гаралт

Хамгийн өндөр байж болох алаг цамхагийн тодорхойлолтыг хэвлэнэ. Эхний мөрөнд цамхагийн өндөрийг хэвлэх ба хоёр дахь мөрөнд цамхагийг бүрдүүлж байгаа шооны тоог, харин гурав дахь мөрөнд цамхагт орсон шоонуудын дугаарыг (дээрээс нь доош) зайгаар тусгаарлан хэвлэнэ үү. Шоонууд оролтонд өгөгдсөн дарааллаараа $1$-ээс $n$ хүртэл дугаарлагдана.

Хэрвээ хамгийн алаг өндөр цамхгийг барих олон янзын хувилбар байвал алийг нь ч хэвлэсэн болно.

64 битийн бүхэл тоог унших болон бичихдээ "%lld" тодорхойлогчийг битгий ашиглаарай. $cin$, $cout$ эсвэл "%I64d" тодорхойлогчийг ашиглаарай.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
4
1 2
1 3
2 4
3 3
Гаралт
9
3
2 3 1 
Оролт
2
1 1
2 1
Гаралт
2
2
2 1 
Сэтгэгдлүүдийг ачааллаж байна...