D. Хүүдий ба зоос

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

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

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

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

Бага байхдаа та бүхэн хүүдий ба зоосны талаарх таавар сонсож байсан гэж найдаж байна. Ямартаа ч нэг хувилбарыг нь толилуулъя:

Морь 3 хүүдийтэй. Нэг дэх хүүдийн нэг зоостой, хоёр дахь мөн нэг зоостой, харин гурав дахь гурван зоостой. Морь нийтдээ гурван зоостой. Энэ ямар учиртай вэ?

Хариулт нь их энгийн. Гурав дахь хүүдийнд нэг зоос ба нөгөө хоёр хүүдийн нь байгаа.

Энэ бодлого нь үүний өргөтгөл юм. Танд $n$ хүүдий байгаа ба таны нэг дэх хүүдий $a_1$ зоос, хоёр дахь хүүдий $a_2$ зоос , ..., $n$ дэх хүүдий $a_n$ зоос агуулна. Танд нийтдээ $s$ ширхэг зоос байгаа. Хүүдийнүүдийг ямар байдлаар байрлуулбал дээрх байдалтай болохыг эсвэл ийм байх боломжгүй болохыг тогтоо.

Оролт

Эхний мөр $n, s (1\le n,s\le70000)$ тоонуудыг агуулах ба эдгээр нь харгалзан хүүдийний тоо болоод нийт зоосны тоог илэрхийлнэ. Дараагийн мөрөнд хүүдийнүүд дэх зоосны тоог илтгэх $a_1,a_2,...,a_n (1\le a_i\le 70000)$ тоонууд өгөгдөнө.

Гаралт

Ийм байх боломжгүй бол -1 гэж хэвлэ.

Үгүй бол $n$ мөрөнд хүүдий бүрийн байдлыг тодорхойлж хэвлэ: $i$ дэх мөр $i$ дэх хүүдийний байдлыг илтгэнэ. Мөрөн дэх эхний тоо $c_i (0\le c_i\le a_i)$ нь $i$ дэх хүүдийнд шууд утгаараа хэдэн зоос байгааг илэрхийлнэ.($i$ дэх хүүдийн дотор байгаа хүүдийн доторх зоосыг авч үзэхгүй) Энэ мөрөн дэх 2 дахь тоо $k_i (0\le k_i\le n)$ нь $i$ дэх хүүдийнд дотор шууд утгаараа хэдэн хүүдий байгааг илтгэнэ. ($i$ дотор байгаа хүүдийнүүдийн дотоод хүүдийнүүдийг авч үзэхгүй) Дараагаар нь энэ мөр нь $k_i$ширхэг бүхэл тоо агуулах ба эдгээр нь $i$ дэх хүүдийн доторх хүүдийнүүдийн дугаар байх ёстой.

Шийдэн дэх нийт зоосны тоо $s$ байх ёстой. Мөн шийдэн дэх $i$ дэх хүүдий нийт $a_i$ зоостой байх ёстой.

Ямар ч хүүдий шууд утгаараа нэгээс олон хүүдийн дотор байж болохгүй. Хүүдийнүүд бие биенийхээ дотор олон давхар үүсгэн орсон байж болно(2 дахь жишээ тестийг харна уу). Олон зөв хариулт байвал тэдгээрээс дураар хэвлэхэд хангалттай.

Орчуулсан: Төрбат

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

Оролт
3 3
1 3 1
Гаралт
1 0
1 2 3 1
1 0
Оролт
3 3
1 3 1
Гаралт
1 0
2 1 3
0 1 1
Оролт
1 2
1
Гаралт
-1
Оролт
8 10
2 7 3 4 1 3 1 2
Гаралт
2 0
1 2 1 4
0 2 7 8
0 2 5 6
1 0
3 0
1 0
2 0

Тэмдэглэл

The pictures below show two possible ways to solve one test case from the statement. The left picture corresponds to the first test case, the right picture corresponds to the second one.

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