Soyğun

Olimpiya ölkəsində bank sistemi çox inkişaf edib, buna görə də sakinlər öz yığımlarını məmnuniyyətlə banka qoyurlar. Cəmi N bank var və onlar sırayla düzülüb. i nömrəli bankda a[i] tuqrik saxlanılır. Başlanğıcda banklarda oğurluğun qarşısını ala biləcək təhlükəsizlik sistemi yoxdur. Lakin məlumdur ki, əgər d nömrəli günün axşamı b nömrəli bank soyulubsa, ertəsi günün səhəri qonşu banklarda (b − 1 və b + 1) təhlükəsizlik sistemi quraşdırılacaq və bundan sonra onları soymaq mümkün olmayacaq. d + i (i > 0) nömrəli günün səhəri b − i və b + i banklarında təhlükəsizlik sistemi quraşdırılacaq. Bu proses bütün banklar oğurluqdan qorunana qədər davam edəcək. Soyulmuş bankı bir daha soymaq mümkün deyil. Təəssüf ki, Olimpiya ölkəsində hətta cinayətkarlar da olimpiada məsələlərini həll etməklə məşğuldurlar, buna görə də hökumət əmindir ki, kimsə soyğunçuluq seriyası planlaşdırsa, bunu optimal şəkildə edəcək, yəni təhlükəsizlik sistemi quraşdırılmadan əvvəl soyulacaq banklarda tuqriklərin ümumi sayını maksimumlaşdıracaq. Bundan əlavə, məlumdur ki, cinayətkarlar bir gündə bir bankdan artıq soyğun etmir və yalnız axşam fəaliyyət göstərirlər.

Bank sistemi, soyğunçuluqdan mümkün zərərləri təhlil edərək, M+1 pul yerləşdirmə variantını ardıcıl olaraq nəzərdən keçirir. Hər bir variant əvvəlkindən bir bankda olan pulun miqdarı ilə fərqlənir.

Tapşırıq

Banklarda pul yerləşdirmə variantlarının hər biri üçün soyğunçuluqdan maksimum mümkün itkiləri hesablayan proqram yazın.

Giriş məlumatları

Giriş məlumatlarının ilk sətirində N və M ədədləri — bankların sayı və tuqriklərin miqdarının dəyişdirilməsi əməliyyatlarının sayı verilir. Növbəti sətirdə banklardakı başlanğıc tuqriklərin miqdarını göstərən N ədəd a[i] verilir. Daha sonra M sətir gəlir, hər birində B və T ədədləri yazılıb, bu da növbəti əməliyyatdan sonra B nömrəli bankda T tuqrik olacağını göstərir.

Çıxış məlumatları

Çıxış məlumatlarında hər bir i (0 ≤ i ≤ M) üçün ayrı sətirdə cinayətkarların i əməliyyatından sonra oğurlaya biləcəyi maksimum tuqriklərin miqdarını yazın.

Qiymətləndirmə

Test dəsti 3 blokdan ibarətdir, bunlar üçün əlavə olaraq aşağıdakı şərtlər yerinə yetirilir:

1. 10 % bal: 1 ≤ N, M ≤ 8.

2. 20 % bal: 1 ≤ N, M ≤ 1000.

3. 70 % bal: 1 ≤ N, M ≤ 100 000.

İzah. Aşağıda verilən sxemdə 0 soyulmuş bankı, -1 isə təhlükəsizlik sistemi quraşdırılmış bankı göstərir.

Başlanğıc yerləşdirməyə uyğun olaraq soyğunçuların hərəkətləri belə olacaq:

6 7 5 6 2 2 4 — başlanğıc vəziyyət;

6 7 5 0 2 2 4 — dördüncü bank soyuldu (6 tuqrik);

6 7 -1 0 -1 2 4 — ertəsi gün səhər qonşu banklarda təhlükəsizlik sistemi quraşdırıldı;

6 0 -1 0 -1 2 4 — ikinci bank soyuldu (7 tuqrik);

-1 0 -1 0 -1 -1 4 — təhlükəsizlik sistemi birinci bankda (ikinci bankın soyulması səbəbindən) və altıncı bankda (dördüncü bankın iki gün əvvəl soyulması səbəbindən) quraşdırıldı;

-1 0 -1 0 -1 -1 0 — sonuncu bank soyuldu (4 tuqrik).

Ümumilikdə soyğunçular 17 tuqrik əldə etdilər.

Son yerləşdirmə belə olacaq: 6 7 5 6 2 5 6. Soyğunçular cəmi 6 + 7 + 6 = 19 tuqrik əldə edə bilərlər, əgər dördüncü, ikinci və sonra yeddinci bankları soyarlarsa.