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

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

制約

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

入力例 1

3 3
19 4 5
2 6 2

出力例 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 の制約を満たす．

入力例 2

2 1
9 7
2 6

出力例 2

7

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

入力例 3

5 60000
630510219 369411957 874325200 990002527 567203997
438920902 634940661 593780254 315929832 420627496

出力例 3

41397427274960

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

入力例 4

4 25
1 2 3 4
1 2 3 4

出力例 4

48

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