Skip to content
Sign in

自習 (Self Study)

Unrated
日本語

Language

Contribute a translation
Time limit
1000 ms
Memory limit
512 MB
Submissions
0
Correct
0
Solved by
0
AC rate
—

Statement

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\) 学期の授業がすべて終わると，期末試験が行われる．ビ太郎はその試験で赤点を取りたくないので，試験が行われる時点で，理解度が最も小さい科目の理解度をできるだけ大きくしたい．

学期の長さ，科目数と理解度の増加分が与えられたとき，試験が行われる時点での理解度の最小値として考えられる最大の値を求めるプログラムを作成せよ．

Input

入力は以下の形式で標準入力から与えられる．入力される値はすべて整数である．

\(N\) \(M\)
\(A_1\) \(A_2\) \(\cdots\) \(A_N\)
\(B_1\) \(B_2\) \(\cdots\) \(B_N\)

Output

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

Constraints

  • \(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\))．

Subtasks

  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\) 点) 追加の制約はない．

Examples

Sample input 1
3 3
19 4 5
2 6 2
Sample output 1
18

たとえば次のような方法で勉強をすると，試験が行われる時点で，科目 \(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 input 2
2 1
9 7
2 6
Sample output 2
7

この入出力例は小課題 \(1, 3, 5\) の制約を満たす．

Sample input 3
5 60000
630510219 369411957 874325200 990002527 567203997
438920902 634940661 593780254 315929832 420627496
Sample output 3
41397427274960

この入出力例は小課題 \(3, 5\) の制約を満たす．

Sample input 4
4 25
1 2 3 4
1 2 3 4
Sample output 4
48

この入出力例は小課題 \(2, 3, 4, 5\) の制約を満たす．

Notes

JOI 2022 · JCIOI · CC BY-SA 4.0

Tags

No tags yet

Source