Bowling for Numbers

Στον Διαγωνισμό Καναδικού Καρναβαλιού (Canadian Carnival Competition) (CCC), παίζεται ένα δημοφιλές παιχνίδι, το ~Bowling\;for\;Numbers~. Ένας μεγάλος αριθμός από κορύνες μπόουλινγκ τοποθετείται σε μια σειρά. Κάθε κορύνα έχει τυπωμένο έναν αριθμό, ο οποίος είναι το σκορ που επιτυγχάνεται αν μια ρίψη ανατρέψει τη συγκεκριμένη κορύνα. Στον παίκτη δίνεται ένας αριθμός από μπάλες του μπόουλινγκ- κάθε μπάλα μπόουλινγκ είναι αρκετά μεγάλη ώστε να μπορεί να ανατρέψει αρκετές διαδοχικές και γειτονικές κορίνες.

Για παράδειγμα, μια πιθανή ακολουθία κορύνων είναι: 2 8 5 1 9 6 9 3 2

Αν στην Αλίκη δόθηκαν δύο μπάλες, κάθε μία ικανή να ρίξει τρεις γειτονικές κορύνες, το μέγιστο σκορ που θα μπορούσε να πετύχει η Αλίκη θα ήταν ~39~, το άθροισμα των δύο ρίψεων: ~2 + 8 + 5 = 15~ και ~9 + 6 + 9 = 24~.

Ο Μπομπ έχει μια στρατηγική όπου επιλέγει τη ρίψη που του δίνει το μεγαλύτερο σκορ, και στη συνέχεια επιλέγει επανειλημμένα τη ρίψη που του δίνει το μεγαλύτερο σκορ από τις κορύνες που απομένουν. Αυτή η στρατηγική δεν αποδίδει πάντα τη μέγιστη βαθμολογία, αλλά φτάνει κοντά. Στα δεδομένα ελέγχου, μια τέτοια στρατηγική θα έπαιρνε σκορ ~20%~.

Είσοδος

Η είσοδος αποτελείται από μια σειρά αρχείων ελέγχου. Η πρώτη γραμμή εισόδου περιλαμβάνει τον ~t~, ~1 \le t \le 10~, τον αριθμό των αρχείων ελέγχου στο φάκελο. Η πρώτη γραμμή κάθε αρχείου ελέγχου περιέχει τρεις ακέραιους αριθμούς ~n~ ~k~ ~w~. Πρώτος είναι ο ακέραιος αριθμός ~n~, ~1 \le n \le 30000~, ο αριθμός των κορύνων του μπόουλινγκ. Δεύτερος ο ακέραιος αριθμός ~k~, ~1 \le k \le 500~, ο αριθμός από μπάλες του μπόουλινγκ που έχει στη διάθεσή του κάθε παίκτης. Ο τρίτος και τελευταίος ακέραιος είναι ο ~w~, ~1 \le w \le n~, το πλάτος μιας μπάλας του μπόουλινγκ (ο αριθμός των γειτονικών κορύνων που μπορεί να ανατρέψει). Οι επόμενες n γραμμές κάθε αρχείου ελέγχου περιέχουν έναν μη αρνητικό ακέραιο αριθμό μικρότερο από ~10000~, που δίνει το σκορ των κορύνων, με τη σειρά. Το 20% των δεδομένων ελέγχου θα έχουν μέγεθος μπάλας ~n \le 50~.

Έξοδος

Για κάθε αρχείο ελέγχου, εξάγετε το μέγιστο επιτεύξιμο σκορ από τον παίκτη. Αυτό το σκορ θα είναι εγγυημένα είναι μικρότερο από ένα δισεκατομμύριο.

Παράδειγμα

input

1
9 2 3
2
8
5
1
9
6
9
3
2

output

39