A - 屋台の営業日数 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 233 点

問題文

高橋君は夏祭りの屋台を経営しています。屋台では N 種類の商品を販売しており、 M 人のアルバイトを雇っています。

高橋君は開業資金として S 円を持っています。高橋君は、この資金の範囲内でアルバイトへの日給を支払いながら、できるだけ多くの日数屋台を営業したいと考えています。

各アルバイトにはそれぞれ 1 日あたりの日給が決まっており、 j 番目のアルバイトの日給は B_j 円です。屋台を 1 日営業するには、全アルバイトに日給を支払う必要があります。

一方、屋台の売上は各商品の人気度によって決まります。 i 番目の商品には「人気度」 A_i が設定されており、 1 日あたりの売上は全商品の人気度の合計、すなわち \sum_{i=1}^{N} A_i 円です。

1 日の営業では、売上を得てからアルバイト全員への日給を支払います。つまり、ある日の営業終了時点での所持金の変化は +\left(\sum_{i=1}^{N} A_i\right) - \left(\sum_{j=1}^{M} B_j\right) 円です。

高橋君は、営業日ごとに日給を支払った後の所持金が 0 円未満になってはいけません（ 0 円ちょうどは許容されます）。

高橋君が最大で何日間屋台を営業できるかを求めてください。ただし、もし何日でも営業を続けられる場合は -1 を出力してください。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • 0 \leq S \leq 10^{18}
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq B_j \leq 10^9 (1 \leq j \leq M)
  • 入力はすべて整数である。

入力

N M S
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_M
  • 1 行目には、商品の種類数を表す N 、アルバイトの人数を表す M 、高橋君の開業資金を表す S が、スペース区切りで与えられる。
  • 2 行目には、各商品の人気度を表す A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
  • 3 行目には、各アルバイトの 1 日あたりの日給を表す B_1, B_2, \ldots, B_M が、スペース区切りで与えられる。

出力

高橋君が営業できる最大日数を 1 行で出力せよ。何日でも営業を続けられる場合は -1 を出力せよ。

入力例 1

2 2 10
3 2
4 4

出力例 1

3

入力例 2

3 2 5
10 5 5
8 7

出力例 2

-1

入力例 3

3 4 1000000000000000000
100000000 200000000 300000000
300000000 200000000 150000000 100000000

出力例 3

6666666666

Score : 233 pts

Problem Statement

Takahashi runs a stall at a summer festival. The stall sells N types of products, and he has hired M part-time workers.

Takahashi has S yen as his starting capital. He wants to operate the stall for as many days as possible while paying the daily wages to the part-time workers within this budget.

Each part-time worker has a fixed daily wage. The daily wage of the j-th part-time worker is B_j yen. To operate the stall for one day, he must pay the daily wages to all part-time workers.

On the other hand, the stall's revenue is determined by the popularity of each product. The i-th product has a "popularity" value A_i, and the daily revenue is the sum of the popularity values of all products, i.e., \sum_{i=1}^{N} A_i yen.

During one day of operation, the revenue is earned first, and then the daily wages are paid to all part-time workers. In other words, the change in the amount of money held at the end of a day's operation is +\left(\sum_{i=1}^{N} A_i\right) - \left(\sum_{j=1}^{M} B_j\right) yen.

Takahashi's money after paying the daily wages on each business day must not become less than 0 yen (exactly 0 yen is acceptable).

Determine the maximum number of days Takahashi can operate the stall. If he can continue operating indefinitely, output -1.

Constraints

  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • 0 \leq S \leq 10^{18}
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq B_j \leq 10^9 (1 \leq j \leq M)
  • All inputs are integers.

Input

N M S
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_M
  • The first line contains N representing the number of product types, M representing the number of part-time workers, and S representing Takahashi's starting capital, separated by spaces.
  • The second line contains the popularity values of each product A_1, A_2, \ldots, A_N, separated by spaces.
  • The third line contains the daily wage of each part-time worker B_1, B_2, \ldots, B_M, separated by spaces.

Output

Output the maximum number of days Takahashi can operate the stall in one line. If he can continue operating indefinitely, output -1.

Sample Input 1

2 2 10
3 2
4 4

Sample Output 1

3

Sample Input 2

3 2 5
10 5 5
8 7

Sample Output 2

-1

Sample Input 3

3 4 1000000000000000000
100000000 200000000 300000000
300000000 200000000 150000000 100000000

Sample Output 3

6666666666