Farmer John は最近、$N$ 台（$1 \le N \le 40,000$）の搾乳機を持つ納屋を買いました。番号 $1..N$ で一列です。

機械 $i$ は一日 $M(i)$ 単位（$1 \le M(i) \le 100{,}000$）搾れます。しかし近すぎて、その日 $i$ を使うと両隣は使えません（端は当然隣が一つ）。日ごとに異なる部分集合を選べます。

$D$ 日（$1 \le D \le 50,000$）の最大総量を求めます。各日の初め、一台 $i$ の整備によりその日以降の出力 $M(i)$ を変えられます。毎日の変更から $D$ 日の最大量を求めてください（32 ビット整数に収まらない場合があります）。

入力

• 第 1 行：$N$ と $D$。
• 第 $2..1+N$ 行：第 $i+1$ 行は初期 $M(i)$。
• 第 $2+N..1+N+D$ 行：第 $1+N+d$ 行の整数 $i$、$m$ は第 $d$ 日の初めに $M(i)$ を $m$ にすることを示します。

出力

• 第 1 行：$D$ 日の最大総量。

入出力例

入力 1

5 3
1
2
3
4
5
5 2
2 7
1 10

出力 1

32

注記

5 台の初期出力は 1,2,3,4,5。1 日目に機械 5 を 2 単位にし、以降も同様です。

1 日目の最適値 $2+4 = 6$（$1+3+2$ でも可）、2 日目 $7+4 = 11$、3 日目 $10+3+2=15$ です。

問題作成者：Brian Dean