D. Түрээсийн дугуй

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

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

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

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

$n$ ширхэг сурагч хөвгүүд дугуй унахаар шийджээ. Тэдний хэн нь ч дугуйгүй болохоор тэд хөлсөлж унахаар болжээ.

Түрээсийн газар тэдэнд $m$ ширхэг дугуй санал болгосон байна. Түрээсийн үнэ өөр дугуйнуудын хувьд өөр өөр бөгөөд $j$-р дугуйг хөлслөхөд $p_j$ рублийн үнэтэй болно.

Хөвгүүдийн дундын төсөв нь нийт $a$ рубль байна. Түүнчлэн хөвгүүд тус бүр өөрсдийн гэсэн хувийн мөнгөтэй буюу $i$ дүгээр хүү өөрийн гэсэн $b_i$ рубльтэй юм. Дундын төсөв аль ч сурагчид зарцуулагдаж болох ч хөвгүүн бүрийн хувийн мөнгө зөвхөн тэр хүүгийн дугуйг түрээслэхэд зарцуулагдаж болно.

Хөвгүүн бүр ихдээ нэг дугуй түрээслэх ба дугуйгаа нэгэндээ өгч болохгүй.

Дугуй унах боломжтой хөвгүүдийн хамгийн их тоо хэд вэ? Эдгээр тооны хүүхдэд дугуй унуулахад зарцуулагдах нийт хувийн мөнгөний байж болох хамгийн бага утга хэд вэ?

Оролт

Оролтын эхний мөрөнд $n$, $m$ ба $a$ ($1 ≤ n, m ≤ 10^5$; $0 ≤ a ≤ 10^9$) гэсэн 3 бүхэл тоо байна. Дараагийн мөрөнд $b_i$ нь $i$ дэх хөвгүүний хувийн мөнгийг илэрхийлж байхаар $b_1$, $b_2$, ... , $b_n$ ($1 ≤ b_i ≤ 10^4$) бүхэл тоонуудын дараалал байна. 3 дугаар мөрөнд $p_j$ нь $i$ дэх дугуйны түрээсийн үнийг илэрхийлж байхаар $p_1$, $p_2$, ... , $p_m$ ($1 ≤ p_j ≤ 10^9$) бүхэл тоон дараалал байна.

Гаралт

$r$ нь дугуй түрээслэж чадах хамгийн олон хөвгүүдийн тоо, $s$ нь дугуй түрээслэхэд шаардагдах хамгийн бага хувийн мөнгөний хэмжээ байхаар $r$ ба $s$ 2 ширхэг бүхэл тоог хэвлэнэ. Хэрэв сурагчид огт дугуй түрээслэж чадаагүй бол $r = s = 0$ байна.

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

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

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

Тэмдэглэл

In the first sample both schoolchildren can rent a bike. For instance, they can split the shared budget in half (5 rubles each). In this case one of them will have to pay 1 ruble from the personal money and the other one will have to pay 2 rubles from the personal money. In total, they spend 3 rubles of their personal money. This way of distribution of money minimizes the amount of spent personal money.

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