Батын компани нь N ш ачааны машинтай. Ачааны машин нь ажилд явж мөнгө олдог. Тэдгээр машинуудыг ажилаа дуусах үед зогсоолд тавих хэрэгтэй болдог. Тухайн зогсоол нь төлбөрөө ер бусын аргаар авдаг бөгөөд машины тооноос шалтгаалж хөнгөлөлт үзүүлдэг. Зогсоолд i ш машин тавихад машин тус бүрээс минут тутамд \(A_i\) төгрөг авдаг.

Батын машинууд нь өнөөдөр харилцан адилгүй цагт ирж зогсоод тавьсан бөгөөд бүгд буцаад ажилдаа гарсан. Тэгвэл Бат тэдгээр машинуудын төлбөрт нийт хэдэн төгрөг төлөх ёстой вэ? Та тооцоолж өгч чадах уу?

Оролт:

Эхний мөрөнд Батын машины тоо болох N гэсэн бүхэл тоо өгөгдөнө

2-р мөрөнд тухайн зогсоолын төлбөрийн хэмжээнүүд болох A1, A2, A3, ..., AN гэсэн N ш бүхэл тоо хоосон зайгаар тусгаарлан өгөгдөнө. Эдгээ нь A1 нь 1ш машин зогсоолд тавихад машин бүрээс авах мөнгөн дүн, A2 нь 2ш машин зогсоолд тавихад машин бүрээс авах мөнгөн дүн, ... , AN нь Nш машин тавихад машин бүрээс авах мөнгөн дүнг илэрхийлнэ. Мөн эдгээр төлбөр нь минут тутам авах үнэ юм.

Дараагийн N ш мөрт мөр бүрт ирэх цаг T1, явах цаг T2 гэсэн хоёр бүхэл тоо өгөгдөнө. Эдгээр нь Батын ачааны машины ирэх болон явах цагуудыг (минутаар) илэрхийлнэ. Ирэх цаг нь үргэлж явах цагаас эрт байна.

Гаралт

Батын машинуудаа зогсоолд тавихад нийт хэдэн төгрөг төлөхийг илэрхийлэх нэг бүхэл тоог хэвлэ.

Хязгаарлалт:

• \(0<N<10000000\)
• \(0<Ai<1000; i\in [1..N]\)
• \(0<T1<=T2<10000000\)

Дэд бодлогууд:

Жишээ

Оролт 1

3
5 3 1
1 6
3 5
2 8

Гаралт 1

33

Оролт 2

5
10 8 6 5 4
15 30
25 50
70 80
1 100
3 4

Гаралт 2

1276

Тайлбар:

1-р жишээний хувьд Бат 3 машинтай харин зогсоолд машин хэдэн машин байрлуулахаас хамааран дараах төлбөрийг минут тутам төлөх ёстой

• 1 машин байрлуулбал 1 минут бүрд 5 төг
• 2 машин 1 минут зогсоход машин бүрээс 3 төг
• 3 машин 1 минутад зогсоход машин бүрээс 1 төг

төлөх ёстой гэсэн үг юм.

Батын 3 машин нь дараах цагуудад ирээд явсан гэвэл

1. 1 минутад ирээд 6 минутад явсан гэвэл нийт 5 минут байрласан
2. 3 минутад ирээд 6 явсан гэвэл нийт 3 минут зогссон
3. 2 минутад ирээд 8 явсан гэвэл нийт 6 минут зогссон

Үүний давхцлыг авч үзвэл

• 1-2 хооронд 1-р машин ганцаараа зогсоолд 1 минут тавигдана (1x1x5=5 төг)
• 2-3 хооронд 1, 3 гэсэн 2 ш машин зогсоолд 1 минут тавигдана (2x1x3=6 төг)
• 3-5 хооронд 1, 2, 3 гэсэн 3 машин зогсоолд 2 минут тавигдана (3x2x1=6 төг)
• 5-6 хооронд 1, 3 гэсэн 2 машин зогсоолд 1 минут тавигдана (2x1x3=6 төг)
• 6-8 хооронд 3 дугаартай 1 машин зогсоолд 2 минут тавигдана (1x2x5=10 төг)

Нийт 33 төгрөг болж байна