E. Үнэг ба Хөзөртэй Тоглоом

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

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

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

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

Сиел үнэг найз Жиро үнэгтэйгээ хөзрөөр тоглож байна. Ширээн дээр хэд хэдэн хөзрүүдийг давхарласан $n$ ширхэг овоо байна. Хөзөр бүрт эерэг тоо бичигджээ.

Тоглогчид Сиелээс эхлээд ээлж ээлжээр тоглоно. Сиел өөрийнхөө ээлжинд ямар нэгэн хоосон биш овооноос хамгийн дээд талын $1$ хөзрийг авч болно. Харин Жиро өөрийнхөө ээлжинд ямар нэгэн хоосон биш овооны хамгийн доод талын $1$ хөзөр авч болох юм. Аль ч тоглогчийн хувьд авсан хөзрүүдийнхээ нийлбэр оноог хамгийн их болгох нь тоглоомын зорилго юм. Бүх овооны хөзрийг авч дуусахад тоглоом дуусна.

Сиел, Жиро хоёр хоёулаа хамгийн зөв стратегиэр тоглоно гэж үзвэл тус бүр хэдэн оноо авах вэ?

Оролт

Эхний мөрөнд нэг ширхэг тоо буюу $n$ өгөгдөнө. $(1 \leq n \leq 100)$. Түүний дараа $n$ ширхэг мөрөнд овоо тус бүрийн мэдээлэл өгөгдөнө. $i$ дугаар мөрний хамгийн эхний тоо нь $i$ дугаар овооны хөзрийн тоо $s_i$ $(1 \leq s_i \leq 100)$ байх ба түүний дараа тухайн овооны хөзрүүд дээрх тоо болох $s_i$ ширхэг эерэг тоо $c_1, c_2, .., c_{s_i}$ $(1 \leq c_k \leq 1000)$ нь овоон дахь дээрээс доош дарааллаар өгөгдөнө.

Гаралт

$2$ ширхэг тоо хэвлэнэ. Үүнд: Сиел, Жиро хоёр хоёулаа хамгийн зөв стратегиэр тоглоно гэж үзвэл тус бүрийн нийт авах оноо

Орчуулсан: footman

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

Оролт
2
1 100
2 1 10
Гаралт
101 10
Оролт
1
9 2 8 6 5 9 4 7 1 3
Гаралт
30 15
Оролт
3
3 1 3 2
3 5 4 6
2 8 7
Гаралт
18 18
Оролт
3
3 1000 1000 1000
6 1000 1000 1000 1000 1000 1000
5 1000 1000 1000 1000 1000
Гаралт
7000 7000

Тэмдэглэл

Эхний жишээнд, Сиел $100,1$ гэсэн тоотой хөзрийг, Жиро $10$ гэсэн тоотой хөзрийг авах болно.

Хоёрдугаар жишээнд, Сиел $2, 8, 6, 5, 9$ гэсэн тоотой хөзрүүдийг, Жиро $4, 7, 1, 3$ гэсэн тоотой хөзрүүдийг авах болно.

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