B. Тооцооны туслах ажилтан

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

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

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

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

Боб дэлгүүрт орж $n$ тооны зүйлийг сагсанд хийн тооцоо хийхээр кассыг чиглэн явлаа. Худалдан авсан зүйл бүр нь $c_{i}$ үнээр тодорхойлогдох ба худалдагч тус бүрт $t_{i}$ цаг зарцуулна. Худалдагчийг хэд хэдэн барааны тооцоог хийж байх хооронд Боб сагсанд байгаа бусад зүйлээс хулгайлах боломжтой юм. Нэг бараа хулгайлахын тулд Боб яг 1 секунд зарцуулагдана. Боб худалдагчид өгч ёстой хамгийн бага мөнгөн дүн хэд байх вэ? Боб өөрөө худалдагчид сагсан дахь барааг ямар дарааллаар гаргаж өгөхөө шийднэ гэдгийг санаарай.

Оролт

Оролтын эхний мөр нь $n$ ($1 ≤ n ≤ 2000$) гэсэн тоог агуулна. Дараагийн $n$ мөрүүдэд бараанууд нь $t_{i}$, $c_{i}$ ($0 ≤ t_{i} ≤ 2000, 1 ≤ c_{i} ≤ 10^{9}$) гэсэн хос тоогоор илэрхийлэгдэнэ. Хэрэв $t_{i}$ нь $0$ бол худалдагч $i$ барааны тооцоог хийж байхад Боб ямар ч бараа хулгайлах боломжгүй.

Гаралт

Бобын төлөх ёстой хамгийн бага мөнгөн дүнг ол.

Орчуулсан: Энхгэрэл

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

Оролт
4
2 10
0 20
1 5
1 3
Гаралт
8
Оролт
3
0 1
0 10
0 100
Гаралт
111
Сэтгэгдлүүдийг ачааллаж байна...