概要

高橋君は、所持金 \(S\) 円の範囲内でアルバイトに日給を支払いながら、屋台を最大何日間営業できるかを求める問題です。ただし、毎日の売上から日給を引いた結果がマイナスになる場合、所持金が尽きてしまう可能性があります。

考察

この問題では、1日営業するたびに売上 \(\sum A_i\) を得て、全アルバイトへの日給 \(\sum B_j\) を支払います。そのため、1日あたりの収支は

\[ \text{profit\_per\_day} = \sum_{i=1}^{N} A_i - \sum_{j=1}^{M} B_j \]

となります。

重要な観察

• もし \(\text{profit\_per\_day} \geq 0\) であれば、売上以上の利益があるか、売上と支出が一致しているため、永遠に営業できます。この場合は -1 を出力します。
• そうでない場合（\(\text{profit\_per\_day} < 0\)）、日々の所持金は減少していきます。最終的に所持金が0未満にならない最大日数を求めればよいです。

所持金の変化

\(d\) 日間営業した後の所持金は以下のように表せます：

\[ \text{money} = S + d \cdot \text{profit\_per\_day} \]

ただし、毎日売上を得てから日給を支払うので、途中で所持金が負にならないようにする必要があります。しかし、\(\text{profit\_per\_day}\) が負の場合、所持金は日に日に減っていくため、最初に0未満になるのは最終日と考えて良いです。

したがって、条件は単純に：

\[ S + d \cdot \text{profit\_per\_day} \geq 0 \]

この不等式を満たす最大の整数 \(d\) を求めれば良いです。

なぜ二分探索？

\(d\) の上限が非常に大きい（最大で \(10^{18}\)）ため、線形に試していくと間に合いません。そこで、条件を満たす最大の \(d\) を高速に求めるために 二分探索 を使います。

アルゴリズム

1. 各商品の人気度の合計 \(\sum A_i\) と、アルバイトの日給の合計 \(\sum B_j\) を求めます。
2. \(\text{profit\_per\_day} = \sum A_i - \sum B_j\) を計算します。
3. \(\text{profit\_per\_day} \geq 0\) なら -1 を出力して終了。
4. そうでない場合、二分探索により「所持金が0以上になる最大日数」を探します。
   • 探索範囲：\(0 \leq d \leq 10^{18}\)
   • 条件：\(S + d \cdot \text{profit\_per\_day} \geq 0\)

計算量

• 時間計算量: \(O(N + M + \log(10^{18}))\)
  • 合計の計算に \(O(N + M)\)、二分探索部分で \(O(\log(10^{18}))\)
• 空間計算量: \(O(N + M)\)
  • 入力データをリストで保持するため

実装のポイント

• input() ではなく sys.stdin.read を使って高速入力処理を行う（大きな入力に対応するため）。
• 整数の除算や比較においてオーバーフローに注意する必要はないが、符号に注意すること（profit_per_day は負）。
• 二分探索の終了条件は left <= right として、mid の評価によって left または right を更新する。

## ソースコード

```python
def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    S = int(data[2])
    
    A = list(map(int, data[3:3+N]))
    B = list(map(int, data[3+N:3+N+M]))
    
    total_revenue = sum(A)
    total_cost = sum(B)
    
    if total_revenue >= total_cost:
        print(-1)
        return
    
    # 一日あたりの利益（実際はマイナス）
    profit_per_day = total_revenue - total_cost
    
    # 最大日数を二分探索で求める
    # 所持金が0以上である最大の日数dについて探す
    # d日営業した後の所持金 = S + d * profit_per_day
    # ただし、毎日日給を支払う前に売上有を得るため、制約は
    # S + k * profit_per_day >= 0 for all k in 1 to d
    # すなわち、min(S + k * profit_per_day) >= 0 for k=1..d
    # この最小値はk=dのとき最小（profit_per_day < 0なので）
    # よって、S + d * profit_per_day >= 0
    # d <= ( -S ) / profit_per_day （profit_per_day < 0 なので不等号逆）
    # 実際にdが整数なので、floor( (-S) / profit_per_day )
    # ただし、profit_per_day が負の整数なので、
    # d = floor( (-S) / profit_per_day ) = ( -S - profit_per_day + 1 ) // profit_per_day
    # ではなく、単純に(S // (-profit_per_day))で良いかもしれないが注意
    
    # 安全に二分探索で求める
    left = 0
    right = 10**18
    answer = 0
    
    while left <= right:
        mid = (left + right) // 2
        # mid日間営業した後の所持金
        money = S + mid * profit_per_day
        if money >= 0:
            answer = mid
            left = mid + 1
        else:
            right = mid - 1
            
    print(answer)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。