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$, לשנות $M(i)$ ל-$m$ בתחילת יום $d$.

פלט

• שורה 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