C. Грэг болон түүний найзууд

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

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

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

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

Нэгэн өдөр Грэг болон түүний найзууд ой дундуур алхаж байв. Тэнд Грэгтэй нийлээд $n$ хүн байсан.Дараа нь тэр голын урд ирсэн ба тэд гол гатлахаар шийдэв. Азаар тэдний зогсож байсан газар завьны зогсоол болж таарсан юм.Гэхдээ завь хамгийн ихдээ $K$ кг жин зөөж чадна гэдэг нь мэдэгдэж байв.

Грэг үзэг цаас аваад тэнд байсан хүмүүсийн нэрийг жинтэй нь жагсааж бичив (өөрийгөө оруулаад). Хүмүүсийн биеийн жин $50$ эсвэл $100$ кг байв.Грэг гол гатлахын тулд хамгийн багадаа хэдэн удаа завиар явахыг олж мэдэхийг хүсэв.Завийг чиглүүлж явахад дор хаяж $1$ хүн хэрэгтэй. Голыг гатлахад завинд нийт жин нь $K$ гаас хэтрэхгүй хэдэн ч хүн сууж болно.

Грэг хичнээн төрлийн аргаар гол гатлаж болохыг мэдмээр байлаа. Хэрвээ бусад явалтуудаас өөр хүмүүсийн олонлог тухайн явалтан дээр явах юм бол тэр нь ялгаатай явалт болно (өмнө нь тэр хүмүүсийн олонлог завиар зорчоогүй).

Оролт

Эхний мөрөнд 2 ширхэг $N$ , $k$ ($1 ≤ n ≤ 50, 1 ≤ k ≤ 5000$) бүхэл тоо – $n$ хүмүүсийн тоо (Грэгийг оруулаад) болон $k$ завьны жингийн хязгаар.Дараагийн мөр $n$ бүхэл тоог агуулна – хүмүүсийн жин .Хүмүүсийн жин $50$ кг юмуу $100$ кг байна.

Гаралт

Эхний мөрөнд бүхэл тоог хэвлэнэ – Хамгийн бага зөөлтийн тоо.Хэрвээ бүх хүмүүсийг нөгөө эрэгт гаргах боломжгүй бол $-1$ гэж хэвлэ. $2$-дугаар мөрөнд хамгийн бага байж болох зөөлтийн тоог $1000000007$ ($10^9 + 7$)-д хуваасан үлдэгдэлийг хэвлэ. Хэрвээ бүх хүмүүсийг завьны нөгөө талд гаргах боломжгүй бол $0$ гэж хэвлэ.

[Орчуулга хяналт хийгдээгүй. ^_^ ... Codeforces Mongolian Translation Team]

Орчуулсан: Баттулга

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

Оролт
1 50
50
Гаралт
1
1
Оролт
3 100
50 50 100
Гаралт
5
2
Оролт
2 50
50 50
Гаралт
-1
0

Тэмдэглэл

In the first test Greg walks alone and consequently, he needs only one ride across the river.

In the second test you should follow the plan:

  1. transport two $50$ kg. people;
  2. transport one $50$ kg. person back;
  3. transport one $100$ kg. person;
  4. transport one $50$ kg. person back;
  5. transport two $50$ kg. people.

That totals to $5$ rides. Depending on which person to choose at step 2, we can get two distinct ways.

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