D. Том Хамгийн Их Нийлбэр

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

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

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

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

Ахмед болон Мостафа нар хэдэн жилийн турш маш олон программчлалын тэмцээнүүдэд өрсөлдсөн билээ. Тэдний дасгалжуулагч Фегла тэднээс нэгэн өрсөлдөөнтэй бодлогыг бодож өгөхийг хүссэн бөгөөд мэдээж хэрэг Ахмед уг бодлогыг бодож чадах боловч Мостафа чадахгүй байв.

Уг бодлого нь энгийн бодлоготой төстэй боловч ялгаатай хэлбэртэй бөгөөд мөн ялгаатай шаардлагуудтай байв.

Энгийн бодлогын хувьд танд нэгэн бүхэл тоонуудын цуваа өгөгдөх ба та уг цувааны хувьд нийлбэр нь боломжит хамгийн их байх нэг болон нэгээс олон тооны дараалсан элементүүдийг олох хэрэгтэй юм.

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

Жишээлбэл танд {1, 6, -2}, {3, 3} болон {-5, 1} гэсэн жижиг цуваанууд өгөгдсөн байна гэж үзье. Мөн том цуваанд байх жижиг цуваануудын дугаарууд нь {2, 3, 1, 3} байг. Ингэснээр жижиг цуваануудыг холбон гинжин хэлхээг үүсгэх бөгөөд үр дүнд нь том цувааны жинхэнэ элементүүдийн утга нь {3, 3, -5, 1, 1, 6, -2, -5, 1} болох юм. Мөн уг жишээний хувьд хамгийн их нийлбэр нь 9-тэй тэнцүү байна.

Та Мостафа-д туслан уг бодлогыг бодож өгч чадах уу?

Оролт

Эхний мөрөнд 2 бүхэл тоо $n$ болон $m$ өгөгдөх ба $n$ нь жижиг цувааны тоог ($1 ≤ n ≤ 50$) $m$ нь том цуваанд байх жижиг цуваануудын дугааруудын тоог ($1 ≤ m ≤ 250000$) илэрхийлнэ. Дараа нь $n$ ширхэг мөр өгөгдөнө. Эдгээрийн $i$-р мөр нь бүхэл тоо $l$-ээр ($1 ≤ l ≤ 5000$) эхлэх ба уг тоо нь $i$-р цувааны хэмжээг илэрхийлэх бөгөөд үүний араас тус бүр нь -1000-аас их буюу тэнцүү, 1000-аас бага буюу тэнцүү байх $l$ ширхэг бүхэл тоо өгөгдөнө. Сүүлийн мөрөнд $m$ ширхэг бүхэл тоо өгөгдөх ба эдгээр нь том цуваан дахь жижиг цуваануудын дугааруудыг илэрхийлэх юм. Мөн та жижиг цуваануудыг уг дарааллын дагуу холбон гинжин хэлхээг үүсгэх хэрэгтэй бөгөөд цувааны дугаар болгон нь 1-ээс их буюу тэнцүү, $n$-ээс бага буюу тэнцүү байх юм.

Жижиг цуваанууд нь оролтод өгөгдсөн дарааллынхаа дагуу 1-ээс $n$ хүртэл дугаарлагдсан байна. Өгөгдсөн жижиг цуваануудын зарим нь магадгүй том цуваанд ашиглагдаагүй байж болно.

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

Гаралт

Дээр дүрсэлсний дагуу том цувааг үүсгэсний дараа уг цуваан дахь хамгийн их нийлбэрийг нэг мөрөнд хэвлэнэ үү. Өөрөөр хэлбэл та том цувааны хувьд энгийн бодлогыг бодож хариуг хэвлэх юм. Та нийлбэрийг олохдоо дор хаяж нэг элементийг сонгох хэрэгтэй бөгөөд өөрөөр хэлбэл уг нийлбэр нь хоосон байж болохгүй.

C++ дээр 64-битийн бүхэл тоонуудыг бичихдээ %lld гэсэн тодорхойлогчийг бүү хэрэглэнэ үү. Харин use cout эсвэл %I64d гэсэн тодорхойлогчийг хэрэглэхийг илүүд үзнэ үү.

Орчуулсан: Баатархүү

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

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