index.md

舞會

\begin{figure}[h] \centering \includegraphics[width=5in]{img.jpg} \caption{勤奮的雪乃和打算丟下工作逃跑的伊呂波} \end{figure}

雪乃和伊呂波在準備畢業舞會，準備工作非常繁雜，有 $N$ 項工作需要完成。
為了好好管理進度，雪乃將每項工作都等分成 $K$ 份。
而雪乃和伊呂波一起工作的話，對於第 $i$ 項工作，每天可以完成那項工作的 $a_i$ 份（每項工作每天都會做，且恰好完成 $a_i$ 份，無法把時間挪用給其他工作，就算有一些項目的工作已經完成，也不會增加其他工作的效率）。
但是怕工作做不完，恰好又有 $M$ 筆經費，所以決定把部份工作外包。
每筆經費對於第 $i$ 項工作，可以將那項工作的 $b_i$ 份外包，外包的部分可不計入花費時間直接視為完成。
請問在最佳分配經費的情況下，最少幾天就能完成所有工作（不足一天以一天計）。

\clearpage

輸入

第一行有三個整數 $N, K, M$，
第二行有 $N$ 個整數 $a_i$，
第三行有 $N$ 個整數 $b_i$。

輸出

請輸出最少需要幾天完成所有工作。

輸入限制

• $1 \le N \le 10^5$
• $1 \le K \le 10^9$
• $0 \le M \le 10^9$
• $1 \le a_i \le 10^9$
• $1 \le b_i \le 10^9$

子任務

\subtasks

\clearpage

範例輸入1

3 6 0
1 2 3
2 2 1

範例輸出1

6

範例輸入2

3 6 3
1 2 3
2 2 1

範例輸出2

2

範例說明2

工作	1	2	3
原先工作量	6	6	6
分配經費	2	1	0
外包工作量	4	2	0
剩餘工作量	2	4	6
花費天數	2	2	2

範例輸入3

2 15000 10000
1 2
2 1

範例輸出3

5000