B. Лауренти ба дэлгүүр

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

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

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

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

Бяцхан хүү Лауренти дуртай тоглоом болох Нотаг хэсэг хугацаанд тоглосон ба одоо тэр маш их өлсөж байна. Хүү бяслаг, зайдастай хавчуургатай талх хийхийг хүсч байгаа боловч эхлээд зайдас болон бяслаг авах хэрэгтэй.

Лаурентигийн амьдардаг хот тийм ч том биш. Хотод тус бүрдээ $n$ байшинтай хоёр мөр байдаг. Лауренти хоёр дахь мөрийн хамгийн сүүлийн байшинд амьдардаг. Хотод ганцхан дэлгүүр байдаг ба энэ нь эхний мөрийн хамгийн эхний байшинд байдаг.

Эхний болон хоёрдугаар мөрүүд хоорондоо хотын өргөн чөлөөгөөр тусгаарлагдсан. Хөрш байшингууд хоорондоо гудамжаар тусгаарлагдсан.

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

$i$-р мөрийн $j$-р байшингаас уг мөрийн $(j + 1)$-р байшинруу гардаг явган хүний гарц дээрх гэрлэн дохионы хүлээлгийн цаг нь $a_{ij}$ ($1 ≤ i ≤ 2, 1 ≤ j ≤ n - 1$). Харин нэг мөрийн $j$-р байшингаас нөгөө мөрийн $j$-р байшинруу гардаг явган хүний гарцан дээрх гэрлэн дохионы хувьд хүлээлгийн цаг нь $b_{j}$ ($1 ≤ j ≤ n$). Хотод өөр явган хүний гарц байхгүй.

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

Эхний жишээний зураг.

Лаурентид явган хүний гарц дээр хүлээх нийт цагийн хамгийн бага утгыг тодорхойлоход туслана уу.

Оролт

Оролтын эхний мөрөнд бүхэл тоон утга $n$ ($2 ≤ n ≤ 50$) байх буюу мөр бүрт байх байшингуудын тоо.

Дараагийн хоёр мөр бүрт зайгаар тусгаарлагдсан $n - 1$ бүхэл тоо $a_{ij}$ ($1 ≤ a_{ij} ≤ 100$) байна.

Сүүлийн мөрөнд зайгаар тусгаарлагдсан $n$ бүхэл тоо $b_{j}$ ($1 ≤ b_{j} ≤ 100$) байна.

Гаралт

Лаурентигийн явган хүний гарцууд дээр хүлээх нийт цагийн хамгийн бага утгыг илэрхийлэх бүхэл тоог хэвлэ. Тэр дэлгүүррүү явах болон гэртээ ирэх замдаа өргөн чөлөөг тус бүр нэг л удаа хөндлөн гарна.

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

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

Оролт
4
1 2 3
3 2 1
3 2 2 3
Гаралт
12
Оролт
3
1 2
3 3
2 1 3
Гаралт
11
Оролт
2
1
1
1 1
Гаралт
4

Тэмдэглэл

Эхний жишээг дээр буй зурагт харуулсан байна.

Хоёр дахь жишээн дээр Лаурентигийн зам дараах байдалтай харагдана:

  • Лауренти өргөн чөлөөг хөндлөн гарна, хүлээх цаг нь $3$;
  • Лауренти эхний мөрийн хоёр дахь явган хүний гарцыг ашиглана, хүлээх цаг нь $2$;
  • Лауренти эхний мөрийн эхний явган хүний гарцыг ашиглана, хүлээх цаг нь $1$;
  • Лауренти эхний мөрийн эхний явган хүний гарцыг ашиглана, хүлээх цаг нь $1$;
  • Лауренти өргөн чөлөөг хөндлөн гаран, хүлээх цаг нь $1$;
  • Лауренти хоёрдугаар мөрний хоёр дахь явган хүний гарцыг ашиглана, хүлээх цаг нь $3$. Ингээд нийт хариулт нь $11$.

Сүүлийн жишээн дээр Лауренти бүх явган хүний гарцаар гарах ба хариу нь $4$ байна.

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