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 行：FJ 在 $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