B. Тэмцээний бэлтгэл ажил

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

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

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

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

Удахгүй дэлхийн хамгийн том програмчлалын тэмцээн болох гэж байгаа ба зохион байгуулагчид $m$ ширхэг асуудалтай тулгараад байлаа. Зохион байгуулагч их сургууль энэ асуудлуудыг шийдэхийн тулд сурагчдаа дайчлахаас өөр аргагүй байлаа. Сурагчид өөрсдийгөө ганц найдвар нь гэдгээ мэдсэн тул цалинтай ажиллахыг хүсчээ: $i$-дэх сурагч $c_i$ төгрөг авна. (Хийсэн ажлын хэмжээнээс хамаарахгүйгээр)

Асуудал бүр өөрийн гэсэн хүндрэлийн түвшинтэй ($i$-дэх асуудлын хүндрэлийн түвшин $a_i$) ба сурагч бүр өөрийн гэсэн чадварын үнэлэмжтэй ($i$-дэх сурагчийн чадварын үнэлэмж $b_i$). $i$-дэх сурагч $j$-дэх асуудлыг шийдэхийн тулд түүний чадварын үнэлэмжийг илтгэх тоо нь энэ асуудлын хүндрэлийн түвшнийг илтгэх тооноос багагүй байх ёстой.(Ө.х $b_i \ge a_j$) Сурагч нэг асуудал дээр яг нэг хоног ажилладаг ба өөр асуудал дээр давхар ажиллаж чадахгүй. Мөн асуудлууд бие биеэсээ хамааралгүй, өөрөөр хэлбэл ялгаатай сурагчид ялгаатай асуудлууд дээр нэгэн зэрэг ажиллаж болно.

Их сургууль бүх асуудлаа аль болох хурдан шийдүүлэхийг хүсч байгаа ба тэдэнд $s$ төгрөг л байгаа. Аль сурагчийг аль асуудал дээр ажиллуулахыг тодорхойл.

Оролт

Эхний мөрөнд зайгаар тусгаарлагдсан $n, m , s$ $(1\le n,m\le 10^5, 0\le s\le 10^9)$ — тоонууд өгөгдөх ба эдгээр нь харгалзан сурагчдын тоо, шийдвэл зохих асуудлын тоо, их сургуулийн мөнгөний хэмжээ юм.

Дараагийн мөрөнд зайгаар тусгаардлагд $m$ ширхэг $a_1, a_2, ..., a_m (1\le a_i\le 10^9)$ — тоонууд өгөгдөх ба эдгээр нь асуудлуудын хүндрэлийн түвшинг илтгэнэ.

Дараагийн мөрөнд зайгаар тусгаардлагд $m$ ширхэг $b_1, b_2, ..., b_m (1\le b_i\le 10^9)$ — тоонууд өгөгдөх ба эдгээр нь сурагчдын чадварын үнэлэмжийг илтгэнэ.

Дараагийн мөрөнд зайгаар тусгаардлагд $m$ ширхэг $c_1, c_2, ..., c_m (1\le c_i\le 10^9)$ — тоонууд өгөгдөх ба эдгээр нь сурагчдын шаардах мөнгөний хэмжээг илтгэнэ.

Гаралт

Бүх асуудлыг шийдэж чадахгүй бол "NO" гэж хэвлэ.

Үгүй бол эхний мөрөнд "YES" гэж хэвлээд дараагийн мөрөнд хоорондоо зайгаар тусгаарлагдсан $m$ ширхэг тоог хэвлэнэ: $i$-р тоо нь "i"-дэх асуудлыг шийдэх сурагчийн дугаар. Энэ нь хамгийн хурдан хугацаанд бүх асуудлыг шийдэж байх хариу байх ёстой.(Хамгийн цөөн өдөр зарцууулдаг) Нийт зарцуулах мөнгөний хэмжээ $s$-с хэтэрч болохгүй. Олон хариу байвал аль нэг боломжит хувилбарыг нь хэвлэхэд хангалттай..

Орчуулсан: Төрбат

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

Оролт
3 4 9
1 3 1 2
2 1 3
4 3 6
Гаралт
YES
2 3 2 3
Оролт
3 4 10
2 3 1 2
2 1 3
4 3 6
Гаралт
YES
1 3 1 3
Оролт
3 4 9
2 3 1 2
2 1 3
4 3 6
Гаралт
YES
3 3 2 3
Оролт
3 4 5
1 3 1 2
2 1 3
5 3 6
Гаралт
NO

Тэмдэглэл

Consider the first sample.

The third student (with level 3) must fix the 2nd and 4th bugs (complexities 3 and 2 correspondingly) and the second student (with level 1) must fix the 1st and 3rd bugs (their complexity also equals 1). Fixing each bug takes one day for each student, so it takes 2 days to fix all bugs (the students can work in parallel).

The second student wants 3 passes for his assistance, the third student wants 6 passes. It meets the university's capabilities as it is ready to give at most 9 passes.

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