E. Зохиомол хайрцаг

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

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

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

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

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

Чи Олсыг хайчил тоглоомыг анх удаа тоглож байна гэж төсөөлж үзье. Одоогоор чи зөвхөн эхний хайрцагны үеүд дээр байгаа ("Зохиомол хайрцаг" гэж нэрлэдэг). Үе бүр нь хоёр бүхэл тоогоор тодорхойлогддог: $a_{i}$ нь хэр удаан үеийг давж нэг од авахыг, $b_{i}$ нь хэр удаан үеийг давж хоёр од авахыг $(a_{i} < b_{i})$ илэрхийлнэ.

Чи аль болох хурдан дараагийн хайрцгийг нээхийг хүсэж байгаа. Тэгэхээр чи хамгийн багадаа $w$ одыг цуглуулах хэрэгтэй. Яаж цуглуулах вэ? Үеийг зөвхөн нэг удаа давж болохыг анхаараарай: нэг эсвэл хоёр одтойгоор. Чи бүх үеийг заавал давах албагүй.

Оролт

Эхний мөрөнд хоёр бүхэл тоо $n$ ба $w$ $(1 ≤ n ≤ 3*10^{5}; 1 ≤ w ≤ 2n)$ байна. Энэ тоо нь эхний хайрцагны үеүд ба дараагийн хайрцгийг онгойлгоход хэрэгтэй одны тоо юм. Дараагийн $n$ мөр бүр нь $a_{i}$, $b_{i}$ $(1 ≤ a_{i} < b_{i} ≤ 10^{9})$ хоёр бүхэл тоог агуулна. -- $i$-р үеийн атрибутууд.

Гаралт

Эхний мөрөнд дараагийн хайрцгыг онгойлгоход шаардлагатай хамгийн бага хугацаа $t$-г хэвлэнэ.

Дараагийн мөрөнд $n$ тоог зайгаар тусгаарлан хэвлэнэ. Оновчтой хувилбарын тодорхойлолт:

  • Хэрвээ чамд $i$-р үеийг давахад нэг од хэрэгтэй бол $i$-р тоо нэгтэй тэнцүү байх ёстой;
  • Хэрвээ чамд $i$-р үеийг давахад хоёр од хэрэгтэй бол $i$-р тоо хоёртой тэнцүү байх ёстой;
  • Хэрвээ чи $i$-р үеийг давах хэрэггүй бол $i$-р тоо 0-тэй тэнцүү байна.

Орчуулсан: Даариймаа

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

Оролт
2 3
1 2
1 2
Гаралт
3
12
Оролт
5 3
10 20
5 10
10 20
6 9
25 30
Гаралт
14
01020

Тэмдэглэл

Эхний жишээнд $21$-ийг бас зөв гэж үзнэ.

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