Farmer John's Milk Production

Farmer John has a barn containing N milking machines arranged in a row. Machine i produces M(i) units of milk per day. However, because the machines are installed too close to each other, if machine i is used on a given day, its immediate neighbors cannot be used on that day. Each day, before milking, Farmer John performs maintenance on one chosen machine which updates its daily production value permanently.

For each day, after the update, Farmer John selects a subset of machines (subject to the adjacency restriction) that maximizes the total milk production for that day. Compute the sum of daily maximum milk production over D days.

Note: The answer might not fit into a 32-bit integer.

Mathematically, if the current production values are \(a_1, a_2, \ldots, a_N\), then the daily optimum is given by computing the maximum sum for a subset \(S\subseteq\{1,2,\ldots,N\}\) such that if \(i \in S\) then \(i-1 \notin S\) and \(i+1 \notin S\). This can be formulated using the recurrence:

[ DP[i] = \max{DP[i-1], DP[i-2] + a_i}, \quad DP[0] = 0,; DP[-1] = 0. ]

inputFormat

The first line contains two integers \(N\) and \(D\) (1 \(\le\) \(N\) \(\le\) 40,000, \(1 \le D \le 50,000\)).

The second line contains \(N\) integers representing the initial production values \(M(1), M(2), \ldots, M(N)\) with \(1 \le M(i) \le 100,000\).

Each of the following \(D\) lines contains two integers \(i\) and \(v\) indicating that at the beginning of that day, machine \(i\) has its production updated to \(v\) (\(1 \le i \le N\) and \(1 \le v \le 100,000\)).

outputFormat

Output a single integer representing the total milk production over the \(D\) days, assuming optimal choices are made each day.

sample

3 2
1 2 3
2 5
3 1

10