레이팅 미적용JOI 高校一年の3 学期は,第1 週から第M 週までのM 週間にわたってN 科目の授業が行われる.そ
れぞれの科目には1 からN までの番号が付けられている.また,授業は週N コマあり,各週のi コマ目
(\(1 \le i \le N\)) には科目i の授業が行われる.
高校一年生のビ太郎は,\(N \times M\) 個のコマそれぞれにおいて,以下のいずれかの行動をとることができる.
• 行動1:そのコマの授業に出席する.科目i (\(1 \le i \le N\)) の授業に1 コマ出席した場合,その科目の理
解度がAi 増加する.
• 行動2:そのコマの授業に出席せず,科目を自由に1 つ選んで自習を行う.科目i (\(1 \le i \le N\)) の自習
を1 コマ行った場合,その科目の理解度がBi 増加する.
ただし,最初の時点では全科目について理解度が0 であるものとする.また,放課後は競技プログラミン
グの練習に費やしたいので,授業時間以外に勉強をしないものとする.
3 学期の授業がすべて終わると,期末試験が行われる.ビ太郎はその試験で赤点を取りたくないので,試
験が行われる時点で,理解度が最も小さい科目の理解度をできるだけ大きくしたい.
学期の長さ,科目数と理解度の増加分が与えられたとき,試験が行われる時点での理解度の最小値として
考えられる最大の値を求めるプログラムを作成せよ.
• 1 ≦N ≦300 000.
第21 回日本情報オリンピック(JOI 2021/2022) 本選
2022 年2 月13 日(オンライン開催)
• 1 ≦M ≦1 000 000 000.
• 1 ≦Ai ≦1 000 000 000 (\(1 \le i \le N\)).
• 1 ≦Bi ≦1 000 000 000 (\(1 \le i \le N\)).
- (10 点) M = 1.
- (25 点) N × M ≦300 000,Ai = Bi (\(1 \le i \le N\)).
- (27 点) N × M ≦300 000.
- (29 点) Ai = Bi (\(1 \le i \le N\)).
- (9 点) 追加の制約はない.
入力は以下の形式で標準入力から与えられる.入力される値はすべて整数である.
N M
A1 A2 · · · AN
B1 B2 · · · BN
標準出力に,試験が行われる時点での理解度の最小値として考えられる最大の値を1 行で出力せよ.
3 3
19 4 5
2 6 2
18
2 1
9 7
2 6
7
5 60000
630510219 369411957 874325200 990002527 567203997
438920902 634940661 593780254 315929832 420627496
41397427274960
4 25
1 2 3 4
1 2 3 4
48