D. Илгээмж хүргэлт

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

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

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

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

Жонни ачааны машин жолооддог ба гэрээсээ төвийн дүүрэгт илгээмж хүргэж өгөх ёстой. Түүний гэр тоон шулуун дээр $0$ цэг дээр байрладаг ба төвийн дүүрэг $d$ цэг дээр байрладаг.

Жоннигийн машины шатахууны сав $n$ литрийн багтаамжтай ба анх дүүрэн байна. Тэр явж буйтай зэрэгцэн түүний машин явсан замын нэгж бүрт нэг литр шатахуун зарцуулна. Үүгээр барахгүй төвийн дүүрэг орох замд ялгаатай газар байрласан $m$ ширхэг шатахуун түгээх станцууд байдаг. $i$-р шатахуун түгээх станц тоон шулуун дээр $x_{i}$ цэг дээр байрлах ба литрийг нь $p_{i}$ доллараар борлуулах хязгааргүй шатахуунтай. Жоннигийн илгээмжээ хүргэж өгөхөд шаардлагатай шатахуун хийлгэхэд зарцуулах мөнгөний хамгийн бага хэмжээг ол.

Оролт

Оролтын эхний мөрөнд зайгаар тусгаарлагдсан гурван бүхэл тоон утгууд $d$, $n$, $m$ ($1 ≤ n ≤ d ≤ 10^{9}$, $1 ≤ m ≤ 200 000$) байх ба харгалзан төвийн дүүрэг хүртэлх зай, шатахууны савны эзэлхүүн, шатахуун түгээх газруудын тоо юм.

Дараагийн $m$ мөр бүрт хоёр бүхэл тоон утга $x_{i}$, $p_{i}$ ($1 ≤ x_{i} ≤ d - 1$, $1 ≤ p_{i} ≤ 10^{6}$) байх ба $i$-р шатахуун түгээх станцын байрлал болон шатахууны үнэ юм. Шатахуун түгээх станцуудын байрлал бүгд өөр өөр байна.

Гаралт

Илгээмжийг хүргэхэд шаардлагатай хамгийн бага зардлыг хэвлэ. Илгээмжийг хүргэж өгч чадахгүй бол $-1$-г хэвлэ.

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

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

Оролт
10 4 4
3 5
5 8
6 3
8 4
Гаралт
22
Оролт
16 5 2
8 2
5 1
Гаралт
-1

Тэмдэглэл

Эхний жишээн дээр Жоннигийн машин $4$ литр шатахуун хадгалж чадна. Тэр эхний шатахуун түгээх станц хүртэл замын $3$ нэгж газар явна, $2$ литр шатахуун авна(шатахууны сав нийтдээ $3$ литр шатахуунтай болно), ингээд гурав дахь шатахуун түгээх станц хүртэл дахиад $3$ нэгж зам явна, эндээс $4$ литр шатахуун худалдаж авч саваа дүүргэнэ, тэгээд төвийн дүүрэг хүртэл шууд явна. Түүний нийт зардал $25 + 43 = 22$ доллар болно.

Хоёр дахь жишээн дээр Жонни төвийн дүүрэгт очих боломж байхгүй, түүний шатахууны сав сүүлийн шатахуун түгээх станцаас төвийн дүүрэг хүртэл хангалттай шатахуун авч явж чадахгүй.

Сэтгэгдлүүдийг ачааллаж байна...