C. Дима ба Салад

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

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

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

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

Дима, Инна, Сережа 3 нэг өрөөнд хамт сууж байна. Мэдээж хэн явах хэрэгтэй нь ойлгомжтой. Ингээд Сережаг явуулахын тулд Инна салад хийж, анхааруулга өгөхөөр болжээ.

Дима, Сережа хоёрт хөргөгчинд нь $n$ ширхэг жимс байгаа. Жимс болгонд амт, калори гэсэн $2$ хэмжигдэхүүн бий. Инна салад хийхээр шийдсэн ба хөргөгчинд байгаа жимснээс ашиглахаар болжээ. Инна жимс сонгохдоо дараах дүрмийг баримталжээ: нийт жимсний амтыг нийт калоритой харьцуулсан харьцаа нь яг $k$ гарах ёстой. Өөрөөр хэлбэл . Энд $a_j$ нь сонгосон $j$ жимсний амт, $b_j$ нь калори.

Инна жимсээ сонгоогүй байгаа ба түүний дүрмийг биелүүлж байхаар сонгосон жимсний нийлбэр амт нь хамгийн их байхаар жимснүүдийг яаж сонгож болохыг мэдэхийг хүсэж байгаа. Иннад энэхүү хоолны жорыг гаргаж авахад туслаач!

Инна Димад хайртай болохоор ядаж нэг жимсээр салад хийхийг хүсэж байгаа.

Оролт

Эхний мөр $n$, $k$ ($1 ≤ n ≤ 100$, $1 ≤ k ≤ 10$) хоёр тоог агуулна. Хоёрдох мөр жимснүүдийн амтыг агуулсан $n$ ширхэг тоо $a_1$, $a_2$, ... , $a_n$ ($1 ≤ a_i ≤ 100$). Гуравдах мөр нь $n$ ширхэг тоо болох жимснүүдийн калори $b_1, b_2, ... , b_n$ ($1 ≤ b_ i ≤ 100$)-г агуулна. $i$-р жимс $a_i$ амттай, $b_i$ калоритой.

Гаралт

Хэрвээ Иннад ямар ч шаардлага хангах салад хийх боломж байхгүй бол "-1"-г хэвлэнэ. Бусад тохиолдолд хамгийн их боломжит амтны нийлбэр болох ганц тоог хэвлэ.

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

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

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

Тэмдэглэл

In the first test sample we can get the total taste of the fruits equal to 18 if we choose fruit number 1 and fruit number 2, then the total calories will equal 9. The condition fulfills, that's exactly what Inna wants.

In the second test sample we cannot choose the fruits so as to follow Inna's principle.

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