C. Аня ба сүнснүүд

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

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

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

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

Аня аймшгийн кино үзэх дуртай. Өнөө орой Аня дээр $m$ ширхэг сүнс зочлон ирнэ. Аня уулзалтуудад зориулж олон лаа бэлджээ (лаа болгон тодорхой $t$ секунд асдаг). Охинд лааг асаахын тулд нэг секунд шаардагдана. Энгийнээр Аня лааг асаахад $1$ секунд болох бөгөөд дараа нь лаа яг $t$ секунд ассаны дараа лааг дахиж ашиглах боломжгүй болно.

Аня сүнс болгоны ирэх цагийг тодорхой мэдэж байгаа. $i$ дэхь уулзалт шөнө дундаас хойш $w_{i}$ секундын дараа эхэлнэ. Бүх $w_{i}$ хоорондоо ялгаатай. Уулзалт болгон яг нэг секунд үргэлжилнэ.

Уулзалт болгонд дор хаяж $r$ ширхэг лаа асаалттай байх ёстой бол хамгийн багадаа хэдэн лаа хэрэгтэй вэ? Ямар ч бүхэл секундэнд лааг асаах боломжтой.

Оролт

Эхний мөрөнд гурван ширхэг бүхэл тоо $m$, $t$, $r$ байна. ($1 ≤ m, t, r ≤ 300$). Энэ нь харгалзан Аня дээр зочлох сүнсний тоо, лааны асах хугацаа, уулзалт болгонд асаалттай байх ёстой лааны тоо.

Дараагийн мөрөнд $m$ ширхэг зайгаар тусгаарлагдсан $w_{i}$ тоо өгөгдөнө. ($1 ≤ i ≤ m$, $1 ≤ w_{i} ≤ 300$). Энэ нь шөнө дундаас хойш $w_{i}$ дэхь секундэд $i$ дэхь сүнс ирэхийг тодорхойлно. Бүх $w_{i}$ нь хоорондоо ялгаатай, бүгд өсөх дараалаар өгөгдөнө.

Гаралт

Хэрвээ уулзалт болгонд $r$ ширхэг лааг асаалттай байлгах боломжтой бол, Аняд хамгийн багадаа хэдэн лаа хэрэгтэй вэ? Энэ тоог хэвлэ.

Хэрвээ боломжгүй бол "-1" гэж хэвлэнэ үү.

Орчуулсан: Энхлут

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

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

Тэмдэглэл

Аня уулзалтын үеэр лаа асааж болно. Гэхдээ энэ лаа энэ уулзалтанд ассан гэж тооцогдохгүй.

Лааг асаахын тулд яг нэг секунд шаардах бөгөөд үүний дараагаас лааг асаж байгаа гэж тооцно. Хэрвээ Аня лааг $х$ секундэд асааж эхэлсэн бол лаа $х+1$ секунд эхэлснээс $х+t$ секунд дуустал тасралтгүй асна.

Эхний жишээнд $3$-н лаа хангалттай. Жишээ нь: Аня лааг шөнө дундаас $3$ дахь, $5$ дахь, $7$ дахь секундуудэд асаана.

Хоёр дахь жишээнд $1$ лаа хангалттай. Жишээ нь: Аня лааг шөнө дундаас өмнө нэг секундэнд лааг асаана.

Гурав дахь жишээ тестэнд хариу нь "-1". Учир нь секунд болгонд хамгийн ихдээ нэг лааг асааж чадна. Харин сүнс зочлох үед Аняд $3$ лааг зэрэг асаах шаардлага гарна.

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