팀 빌딩

$N$명의 프로그래머로 팀을 꾸리려고 합니다. $i$번째 프로그래머($1 \le i \le N$)의 실력 수준은 음이 아닌 정수 $s[i]$입니다. 중요한 것은 프로그래머를 고용하는 순서입니다.

각 프로그래머에게는 작업률(workrate)과 동기(motivation)라는 두 정수 값이 있습니다. 두 값은 고용될 때 모두 $0$이며, 이후 새 팀원이 들어오면 증가할 수 있습니다. 새 프로그래머를 고용하면 다음 순서로 일이 일어납니다.

1. 새 프로그래머가 작업률과 동기가 모두 $0$인 상태로 팀에 합류합니다.
2. 이미 고용된 다른 프로그래머 각각의 작업률이 그 사람의 동기만큼 증가합니다.
3. 이미 고용된 다른 프로그래머 각각의 동기가 새 프로그래머의 실력 수준만큼 증가합니다.

팀의 전력은 모든 팀원의 작업률 합으로 정해집니다. 고용 순서를 최적으로 정했을 때 얻을 수 있는 팀 전력의 최댓값을 구하세요.

실력 수준이 $(0, 2, 2, 3)$ 순서로 고용되면 전력은 $6 + 2 + 0 + 0 = 8$입니다. 반면 $(2, 2, 3, 0)$ 순서로 고용하면 전력은 $7 + 3 + 0 + 0 = 10$이 됩니다.

앞으로 $Q$일 동안 일부 프로그래머의 실력 평가가 바뀌었다는 알림을 받습니다. $i$일이 지난 뒤 프로그래머 $x[i]$의 실력 수준이 $y[i]$로 바뀝니다(이전 값과 같을 수도 있습니다). 바뀐 값은 다시 바뀔 때까지 이후 날에도 그대로 사용됩니다. 오늘부터 매일, 그날 기준의 실력 평가로 $N$명을 모두 고용했을 때 얻을 수 있는 팀 전력의 최댓값을 구하세요.

1행에 $N$과 $Q$가 주어집니다. 2행에는 $s[1], s[2], \dots, s[N]$이 주어집니다. 이어지는 $Q$개의 줄에는 각각 정수 $x[i]$와 $y[i]$가 주어집니다.

$Q + 1$개의 줄에 각 날 이후의 팀 전력 최댓값을 시간 순서대로 한 줄에 하나씩 출력합니다. 처음 상태의 값부터 시작합니다.

• $2 \le N \le 50\,000$
• $1 \le Q \le 100\,000$
• 각 $1 \le i \le N$에 대해 $0 \le s[i] \le 100\,000$.
• 각 $1 \le i \le Q$에 대해 $1 \le x[i] \le N$.
• 각 $1 \le i \le Q$에 대해 $0 \le y[i] \le 100\,000$.