D. Чөлөөт зах

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

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

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

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

Жон саяхан өөрийн хотдоо "Чөлөөт зах" үүсгэн байгуулав. Энэ нь өөрийн өмчийг бусдын эд зүйлээр үнэгүй сольж авдаг газар юм.

Жон өөрийн хотод нийт $n$ бараа байгааг мэднэ (бараа бүр өөр өөр). Та дурын тооны барааг зах дээр авч ирэн тэдгээрийгээ дурын өөр бараагаар сольж болно. Бараа бүр цор ганц байна гэдгийг санаарай. Энэ нь та ${a, b}$ цуглуулгыг ${v, a}$ цуглуулгаар солих боломжгүй гэсэн үг юм. Гэхдээ $p$ бараа $x$, $y$-н алинд нь ч байхгүй бол та $x$ цуглуулгыг $y$ цуглуулгаар сольж болно.

Жон бараа тус бүрийн үнэ $c_i$-г мэддэг. Жоны шударга зан $x$ цуглуулгыг $y$ цуглуулгаар дараах нөхцөл биелж байвал солихыг зөвшөөрөхгүй: $s(x) + d < s(y)$

($s(x)$ нь х цуглуулга дахь бүх бараануудын нийт өртөг)

Өдрийн турш Жон зөвхөн нэг цуглуулгаар ямар нэг зүйл сольж авч болно. Эхний байдлаар түүнд ямар ч бараа байхгүй. Жоны хүсэл бол нийт өртөг нь хамгийн их байх барааны цуглуулгыг авах юм. Ийм цуглуулгын өртөгийг мөн Жон үүнийг олж авах хүртэлх хамгийн бага өдрийн тоог олно уу?

Оролт

Эхний мөрөнд хоосон зайгаар тусгаарлагдсан $n$, $d$ хоёр тоо ($1 ≤ n ≤ 50$, $1 ≤ d ≤ 10^4$) буюу зах дээрх бараануудын тоо, Жоны шударга зангийн хэмжээс тус тус байрлана.

Удаах мөрөнд хоосон зайгаар тусгаарлагдсан $n$ ширхэг $c_i$ ($1 ≤ c_i ≤ 10^4$) тоо байна.

Гаралт

Хоосон зайгаар тусгаарлагдсан хоёр тоо: Жоны хүрч чадах боломжит хамгийн их үнэтэй бараануудын цуглуулга болон түүнд хүрэх хамгийн бага өдрийн тоо байна.

Орчуулсан: Энхдүүрэн

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

Оролт
3 2
1 3 10
Гаралт
4 3
Оролт
3 5
1 2 3
Гаралт
6 2
Оролт
10 10000
10000 9999 1 10000 10000 10000 1 2 3 4
Гаралт
50010 6

Тэмдэглэл

In the first sample John can act like this:

  • Take the first item ($1 - 0 ≤ 2$).
  • Exchange the first item for the second one ($3 - 1 ≤ 2$).
  • Take the first item ($1 - 0 ≤ 2$).
Сэтгэгдлүүдийг ачааллаж байна...