28ος ΠΔΠ B' Φάση Λυκείου
Μονοδιάστατο scrabble (scrabble1d)

Δυο φίλοι, η Μαρία και ο Γιάννης, παίζουν μία παραλλαγή του γνωστού παιχνιδιού Scrabble. Το παιχνίδι αυτό γενικά αποσκοπεί στο σχηματισμό λέξεων και την τοποθέτησή τους σε ένα δισδιάστατο πίνακα, ούτως ώστε κάθε παίκτης να μεγιστοποιεί τους πόντους που παίρνει από κάθε λέξη. Η παραλλαγή όμως που παίζουν οι δύο φίλοι έχει τους εξής απλούς κανόνες:

Ο πίνακας όπου τοποθετούνται οι λέξεις είναι μονοδιάστατος και αποτελείται από \(N\) τετράγωνα, κάθε ένα από τα οποία χωράει ένα γράμμα.
Κάθε παίκτης βάζει συγχρόνως στον πίνακα δύο λέξεις, κάθε μία από τις οποίες έχει μήκος ακριβώς \(K\) γράμματα. Οι λέξεις αυτές δεν μπορούν να επικαλύπτονται, μπορούν όμως να εφάπτονται.
Οι πόντοι που προκύπτουν από κάθε λέξη δεν εξαρτώνται από τα γράμματα της λέξης αλλά από τη θέση στον πίνακα όπου αυτά τοποθετούνται. Σε κάθε τετράγωνο του πίνακα γράφεται πόσους πόντους παίρνει ένας παίκτης, αν τοποθετήσει εκεί ένα γράμμα κάποιας λέξης.

Π.χ. έστω ότι ο πίνακας έχει \(N=10\) τετράγωνα, είναι αρχικά άδειος και οι πόντοι που αντιστοιχούν σε κάθε τετράγωνο είναι οι εξής:

Board empty

Η Μαρία έχει σχηματίσει δύο λέξεις με μήκος \(Κ=3\) γράμματα: «ΝΑΙ» και «ΟΧΙ». Πρέπει τώρα να τις τοποθετήσει στον πίνακα έτσι ώστε να πάρει τους περισσότερους δυνατούς πόντους. Αυτό θα το πετύχει αν για παράδειγμα τις τοποθετήσει ως εξής:

Board filled

Με τον τρόπο αυτό παίρνει \(15+12+10=37\) πόντους από την πρώτη λέξη και \(20+4+10=34\) πόντους από τη δεύτερη, άρα συνολικά \(37+34=71\) πόντους.

Μπορείτε να βοηθήσετε τη Μαρία να τοποθετήσει τις πρώτες δύο λέξεις της ώστε να πάρει τους περισσότερους δυνατούς πόντους;

Πρόβλημα

Να αναπτύξετε ένα πρόγραμμα σε μια από τις Γλώσσες του IOI (Pascal, C, C++, Java) το οποίο, αφού διαβάσει τις τιμές των \(N\) και \(K\) και τους πόντους που αντιστοιχούν σε κάθε τετράγωνο του πίνακα, θα τυπώνει το μέγιστο πλήθος πόντων που μπορεί να πάρει η Μαρία, παίζοντας πρώτη και τοποθετώντας κατάλληλα τις δύο λέξεις της.

Αρχεία Εισόδου

Τα αρχεία εισόδου με όνομα scrabble1d.in είναι αρχεία κειμένου με την εξής δομή. Έχουν ακριβώς δύο γραμμές.

Η πρώτη γραμμή περιέχει δύο ακέραιους \(N\) (το μέγεθος του πίνακα) και \(K\) (το μήκος κάθε λέξης) που χωρίζονται μεταξύ τους με ένα κενό διάστημα.
Η δεύτερη γραμμή περιέχει ακριβώς \(N\) ακέραιους \(P_i\) (\(1 \le i \le N\)) που χωρίζονται μεταξύ τους με ένα κενό διάστημα. Ο ακέραιος \(P_i\) είναι το πλήθος των πόντων που αντιστοιχεί στο \(i\)-οστό τετράγωνο του πίνακα.

Αρχεία Εξόδου

Τα αρχεία εξόδου με όνομα scrabble1d.out είναι αρχεία κειμένου με την εξής δομή. Έχουν ακριβώς μία γραμμή που περιέχει ακριβώς έναν ακέραιο αριθμό, το μέγιστο πλήθος πόντων που μπορεί να πάρει τοποθετώντας τις λέξεις της.

Όρια

\(3 \le N \le 2.000.000\),
\(1 \le K \le N/2\),
\(1 \le P_i \le 1.000.000\), όπου \(1 \le i \le N\)
Μπορείτε να θεωρήσετε ότι το άθροισμα όλων των \(P_i\) δε θα υπερβαίνει το \(1.000.000.000\).

Παραδείγματα Αρχείων Εισόδου - Εξόδου

scrabble1d.in	scrabble1d.out
10 3 2 4 15 12 10 1 1 20 4 10	71

Εξήγηση: Αυτό είναι ακριβώς το παράδειγμα της προηγούμενης σελίδας.

scrabble1d.in	scrabble1d.out
10 3 1 5 20 20 20 15 10 1 1 1	90