E. Өнхрүүлцгээе

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

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

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

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

Тоон тэнхлэг дээр зүүнээс баруун руу таран байрласан $n$ ширхэг $x_{1}, x_{2}, ..., x_{n}$ координатууд дээр байрласан шилэн бөмбөлгүүд өгөгджээ. Эдгээр бөмбөлгүүдийг хязгааргүй жижиг гэж үзэх юм. Та зарим бөмбөлөгийг зүүгээр хатган тогтоож болох ба $i$-р бөмбөлөгийг $c_{i}$ өртөгтэйгээр хатгах юм. Үүнд $c_{i}$ нь сөрөг тоо байж болно. Таныг хатгаж дууссаны дараа бөмбөлөгүүд зүүн тийшээ өнхөрч эхлэх ба дараах дүрмийн дагуу өнхөрнө.

Хэрэв бөмбөлөг зүүгээр хатгагдсан бол хөдлөхгүй, бусад тохиолдолд өнхөрч явсаар зүүгээр хатгагдсан бөмбөлөг хүрээд тэндээ зогсох юм. Хэрэв зүүгээр хатгагдаагүй бөмбөлөгийн зүүн талд ямар ч зүүгээр хатгагдсан бөмбөлөг байхгүй бол уг бөмбөлөг нь зүүн тийшээгээ хязгааргүй өнхрөх ба та үүний төлөө хязгааргүй их торгууль төлөх болно. Хэрэв ямар ч бөмбөлөг хязгааргүй өнхрөхгүй бол төлөх торгууль нь дараах хоёр нийлбэр дүнгээс бүрдэнэ:

  • Зүүгээр хатгасан зардлуудын нийт дүн
  • Зүүгээр хатгагдаагүй бөмбөлөг бүрийн явсан замын уртуудын нийлбэр (энэ нь тэдгээрийн анхны байрлал болон сүүлийн байрлал 2-ын ялгаварын абсолют утга байна)

Таны ажил бол өгөгдсөн бөмбөлөгүүдийн хувьд таны төлөх торгуулийн хэмжээ аль болох бага байхаар зүүгээр хатгах юм.

Оролт

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

Гаралт

Хамгийн бага торгуулийн хэмжээг илэрхийлэх ганц тоог хэвлэнэ.

Орчуулсан: Баатархүү

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

Оролт
3
2 3
3 4
1 2
Гаралт
5
Оролт
4
1 7
3 1
5 10
6 1
Гаралт
11
Сэтгэгдлүүдийг ачааллаж байна...