AT_joi2022ho_b 自習 (Self Study)

[problemUrl]: https://atcoder.jp/contests/joi2022ho/tasks/joi2022ho_b JOI 高校一年の $ 3 $ 学期は，第 $ 1 $ 週から第 $ M $ 週までの $ M $ 週間にわたって $ N $ 科目の授業が行われる．それぞれの科目には $ 1 $ から $ N $ までの番号が付けられている．また，授業は週 $ N $ コマあり，各週の $ i $ コマ目 ($ 1\ \leqq\ i\ \leqq\ N $) には科目 $ i $ の授業が行われる． 高校一年生のビ太郎は，$ N\ \times\ M $ 個のコマそれぞれにおいて，以下のいずれかの行動をとることができる． - 行動 $ 1 $：そのコマの授業に出席する．科目 $ i $ ($ 1\ \leqq\ i\ \leqq\ N $) の授業に $ 1 $ コマ出席した場合，その科目の理解度が $ A_i $ 増加する． - 行動 $ 2 $：そのコマの授業に出席せず，科目を自由に $ 1 $ つ選んで自習を行う．科目 $ i $ ($ 1\ \leqq\ i\ \leqq\ N $) の自習を $ 1 $ コマ行った場合，その科目の理解度が $ B_i $ 増加する． ただし，最初の時点では全科目について理解度が $ 0 $ であるものとする．また，放課後は競技プログラミングの練習に費やしたいので，授業時間以外に勉強をしないものとする． $ 3 $ 学期の授業がすべて終わると，期末試験が行われる．ビ太郎はその試験で赤点を取りたくないので，試験が行われる時点で，理解度が最も小さい科目の理解度をできるだけ大きくしたい． 学期の長さ，科目数と理解度の増加分が与えられたとき，試験が行われる時点での理解度の最小値として考えられる最大の値を求めるプログラムを作成せよ． - - - - - -

入力は以下の形式で標準入力から与えられる．入力される値はすべて整数である． > $ N $ $ M $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_N $ $ B_1 $ $ B_2 $ $ \cdots $ $ B_N $

標準出力に，試験が行われる時点での理解度の最小値として考えられる最大の値を $ 1 $ 行で出力せよ． - - - - - -

### 制約 - $ 1\ \leqq\ N\ \leqq\ 300\,000 $． - $ 1\ \leqq\ M\ \leqq\ 1\,000\,000\,000 $． - $ 1\ \leqq\ A_i\ \leqq\ 1\,000\,000\,000 $ ($ 1\ \leqq\ i\ \leqq\ N $)． - $ 1\ \leqq\ B_i\ \leqq\ 1\,000\,000\,000 $ ($ 1\ \leqq\ i\ \leqq\ N $)． ### 小課題 1. ($ 10 $ 点) $ M\ =\ 1 $． 2. ($ 25 $ 点) $ N\ \times\ M\ \leqq\ 300\,000 $，$ A_i\ =\ B_i $ ($ 1\ \leqq\ i\ \leqq\ N $)． 3. ($ 27 $ 点) $ N\ \times\ M\ \leqq\ 300\,000 $． 4. ($ 29 $ 点) $ A_i\ =\ B_i $ ($ 1\ \leqq\ i\ \leqq\ N $)． 5. ($ 9 $ 点) 追加の制約はない． - - - - - - ### Sample Explanation 1 たとえば次のような方法で勉強をすると，試験が行われる時点で，科目 $ 1,\ 2,\ 3 $ の理解度がそれぞれ $ 19,\ 18,\ 19 $ となる． - 第 $ 1 $ 週の $ 1 $ コマ目は，科目 $ 2 $ の自習を行う． - 第 $ 1 $ 週の $ 2 $ コマ目は，科目 $ 2 $ の自習を行う． - 第 $ 1 $ 週の $ 3 $ コマ目は，科目 $ 3 $ の授業に出席する． - 第 $ 2 $ 週の $ 1 $ コマ目は，科目 $ 1 $ の授業に出席する． - 第 $ 2 $ 週の $ 2 $ コマ目は，科目 $ 3 $ の自習を行う． - 第 $ 2 $ 週の $ 3 $ コマ目は，科目 $ 3 $ の授業に出席する． - 第 $ 3 $ 週の $ 1 $ コマ目は，科目 $ 3 $ の自習を行う． - 第 $ 3 $ 週の $ 2 $ コマ目は，科目 $ 2 $ の自習を行う． - 第 $ 3 $ 週の $ 3 $ コマ目は，科目 $ 3 $ の授業に出席する． 理解度の最小値を $ 19 $ 以上にする方法は存在しないため，$ 18 $ を出力する． この入出力例は小課題 $ 3,\ 5 $ の制約を満たす． - - - - - - ### Sample Explanation 2 この入出力例は小課題 $ 1,\ 3,\ 5 $ の制約を満たす． - - - - - - ### Sample Explanation 3 この入出力例は小課題 $ 3,\ 5 $ の制約を満たす． - - - - - - ### Sample Explanation 4 この入出力例は小課題 $ 2,\ 3,\ 4,\ 5 $ の制約を満たす．