Wtf

Ας υποθέσουμε ότι σας δίνεται ένας πίνακας Α με ~N~ ακεραίους, ID πίνακας με ~N + 1~ ακεραίους από το διάστημα ~[1,\;N - 1]~ και ένας ακέραιος ~R~.

Κάνουμε τον μετασχηματισμό Warshall-Turing-Fourier( dεν είναι αληθινός) στον πίνακα A με τον ακόλουθο τρόπο:

~sum = 0~
~for\;\;i = 1\;\;to\;\;N~
  ~index\;=\;min\{ID[i],\;ID[i+1]\}~
  ~sum\;=\;sum\;+\;A[index]~
  ~rotate\;\;array\;\;A\;\;to\;\;the\;\;right\;\;by\;\;R\;\;places~

~change\;\;the\;\;signs\;\;of\;\;all\;\;elements\;\;in\;\;A~

~for\;\;i = 1\;\;to\;\;N~
  ~index\;=\;max\{ID[i],\;ID[i+1]\}~
  ~index\;=\;index\;+\;1~
  ~sum\;=\;sum\;+\;A[index]~
  ~rotate\;\;array\;\;A\;\;to\;\;the\;\;right\;\;by\;\;R\;\;places~

Σας δίνεται ο πίνακας A και η σταθερά ~R~, αλλά δεν είστε εξοικειωμένοι με το ID πίνακα. Ποια είναι η μεγαλύτερη δυνατή τιμή μεταβλητού αθροίσματος μετά την εκτέλεση του παραπάνω αλγορίθμου;

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τους ακέραιους αριθμούς ~N~ και ~R\;(2 \leq N \leq 3\,000,\;1 \leq R < N)~ από την εργασία.

Η δεύτερη γραμμή εισόδου περιέχει τα στοιχεία του πίνακα A, αντίστοιχα από A[1] έως A[~N~]. Αυτοί είναι ακέραιοι από το διάστημα ~[-10^4,\;10^4 ]~.

Έξοδος

Η πρώτη γραμμή εξόδου πρέπει να περιέχει τη μέγιστη τιμή του αθροίσματος.
Η δεύτερη γραμμή εξόδου πρέπει να περιέχει τον ID πίνακα των ~N + 1~ ακεραίων από το διάστημα ~[1,\;N - 1]~ για το οποίο ο αλγόριθμος εξάγει το μέγιστο άθροισμα. Εάν υπάρχουν πολλοί τέτοιοι πίνακες, εξάγετε οποιονδήποτε.

Εάν μόνο η πρώτη γραμμή είναι σωστή (ανεξάρτητα από το αν είναι τυπωμένη η δεύτερη), θα λάβετε το ~50~% των πόντων για την αντίστοιχη περίπτωση δοκιμής.

Βαθμολογία

Σε περιπτώσεις δοκιμών αξίας ~20~% των συνολικών πόντων, θα κατέχει το ~N \leq 7~.
Σε περιπτώσεις δοκιμών αξίας ~60~% των συνολικών πόντων, θα έχει ~N \leq 300~.

Παραδείγματα

input

5 3
1 -1 1 -1 1

output

10
1 1 1 2 2 3

input

6 5
2 5 4 1 3 5

output

16
3 2 1 1 5 4 1