اشترى 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)$ من ذلك اليوم فصاعدًا. احسب أقصى مجموع حسب التغييرات (قد يتجاوز عددًا صحيحًا من 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 إلى وحدتين، وهكذا.

اليوم 1: الأمثل $2+4 = 6$ (أيضًا $1+3+2$). اليوم 2: $7+4 = 11$. اليوم 3: $10+3+2=15$.

مؤلف المسألة: Brian Dean