Balanced Teams

Συνολικά ~12~ από τις αγελάδες του Γιάννη του αγρότη συμμετέχουν φέτος στους χειμερινούς Μουυλυμπιακούς αγώνες, καθεμία με ένα επίπεδο δεξιοτήτων που χαρακτηρίζεται από έναν ακέραιο αριθμό μεταξύ ~1~ και ~1.000.000~.

Ο Γιάννης θέλει να τις χωρίσει σε ~4~ ομάδες των ~3~, έτσι ώστε οι ομάδες να είναι αρκετά "ισορροπημένες" ως προς τη συνολική δεξιότητα (το επίπεδο δεξιοτήτων μιας ομάδας είναι απλώς το άθροισμα των επιπέδων δεξιοτήτων των αγελάδων της ομάδας). Συγκεκριμένα, θέλει να ελαχιστοποιήσει την τιμή ~S - s~, όπου ~S~ και ~s~ είναι τα μέγιστα και ελάχιστα επίπεδα δεξιοτήτων των ομάδων. Αυτό εξασφαλίζει ότι η διακύμανση μεταξύ της πιο έμπειρης και της λιγότερο έμπειρης ομάδας είναι η μικρότερη δυνατή.

Παρακαλούμε βοηθήστε τον Γιάννη να καθορίσει την ελάχιστη δυνατή τιμή του ~S - s~.

Είσοδος

• Γραμμές ~1..12~: Κάθε γραμμή θα περιέχει το επίπεδο δεξιοτήτων μιας αγελάδας.

Έξοδος

• Γραμμή ~1~: Η ελάχιστη δυνατή τιμή του ~S - s~.

Παράδειγμα

input (bteams.in)

1
2
3
4
5
6
7
8
9
10
11
12

output (bteams.out)

1

Επεξήγηση παραδείγματος:

Μία πιθανή λύση είναι να χωριστούν οι ομάδες ως εξής: ~(12,\;1,\;7)~, ~(9,\;8,\;3)~, ~(10,\;5,\;4)~ και ~(11,\;2,\;6)~. Οι δύο πρώτες ομάδες έχουν συνολική δεξιότητα ~20~ και οι δύο δεύτερες ομάδες έχουν συνολικές δεξιότητες ~19~.