D. Дима ба туулайнууд

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

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

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

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

Димад Иннагийн өгсөн бэлэг таалагдсан. Серёжагаас авсан бэлэг бүр ч их таалагдсан.

Дима Иннагийн бэлгэнд маш их талархсан бөгөөд түүнд $n$ ширхэг молтогчин туулай авч өгөхөөр шийджээ. Инна маш их баяртай байв. Тэр туулайнуудыг нэг мөрөнд жагсаагаад тэднийгээ зүүнээс баруун тийш $1$-ээс $n$ тоогоор дугаарлаад луувангаар хооллож эхлэсэн байна. Инна туулай бүрийг нэг удаа хооллох болсон. Гэвч ямар дарааллаар тэднийг хооллох хэрэгтэй юм бол?

Инна хооллосон туулай бүр нь баярлаж байгааг анзаарчээ. Туулайны баярлах хэмжээ нь туулайг хооллохоос өмнө Иннаг зэргэлдээ туулайнуудыг хооллосон эсэхээс хамаарч байлаа. Инна хэрэв зэргэлдээ туулайнууд хоёул өлсгөлөн байхад туулайг хооллох эсвэл зэргэлдээ туулайнуудын аль нэг нь цатгалан байхад хооллох эсвэл аль аль туулай цатгалан байхад хооллох үеийн баярлах хэмжээг мэддэг болно. $1$ болон $n$ дугаартай туулайнууд харгалзан зүүн болон баруун талдаа туулайгүйн улмаас хэзээ ч аль аль талын туулайнууд цатгалан байх боломжгүйг анхаарна уу.

Инна туулайнуудыг хамгийн ихээр баярлуулж хооллоход туслаарай.

Оролт

Эхний мөрөнд туулайнуудын тоог илэрхийлэх $n$ ($1 ≤ n ≤ 3000$) бүхэл тоо байна. Удаах $3$ мөрөнд тус бүр $n$ ширхэг бүхэл тоонууд байна. Эхний мөрөнд $a_1, a_2, ... , a_n$ бүхэл тоонууд. Дараагийн мөрөнд $b_1, b_2, ... , b_n$ бүхэл тоонууд. $3$ дахь мөрөнд $c_1, c_2, ... , c_n$ бүхэл тоонууд байна. Дараах хязгаарлалтыг хангасан $0 ≤ a_i, b_i, c_i ≤ 10^5$ тоонууд байна.

Эхний мөрөн дэх $a_i$ тоо нь зэргэлдээ хоёр туулайнууд аль аль нь өлсгөлөн үед $i$ дугаартай туулайны баярлах хэмжээ болно. $2$ дахь мөрөн дэх $b_i$ тоо зэргэлдээ хоёр туулайны нэг нь цатгалан байх үед $i$ дугаартай туулайны баярлах хэмжээ болно. $3$ дахь мөрөн дэх $c_i$ тоо зэргэлдээ хоёр туулай аль аль нь цатгалан үед $i$ дугаартай туулайны баярлах хэмжээ болно.

Гаралт

Туулайнуудыг хооллосноор Иннагийн туулайнуудыг баярлуулах боломжтой хамгийн их утгыг нэг мөрөнд хэвлэнэ.

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

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

Оролт
4
1 2 3 4
4 3 2 1
0 1 1 0
Гаралт
13
Оролт
7
8 5 7 6 1 8 9
2 7 9 5 4 3 1
2 3 3 4 1 1 3
Гаралт
44
Оролт
3
1 1 1
1 2 1
1 1 1
Гаралт
4
Сэтгэгдлүүдийг ачааллаж байна...