Tandem Bicycle

Από τα πανάρχαια χρόνια, οι πολίτες του Dmojistan και της Pegland βρίσκονται σε πόλεμο. Τώρα, έχουν επιτέλους υπογράψει ανακωχή. Αποφάσισαν να συμμετάσχουν σε μια βόλτα με ποδήλατα τύπου tandem (δύο θέσεων) για να γιορτάσουν την εκεχειρία. Υπάρχουν ~N~ πολίτες από κάθε χώρα. Πρέπει να κατανεμηθούν σε ζεύγη, έτσι ώστε κάθε ζεύγος να περιέχει ένα άτομο από το Dmojistan και ένα άτομο από την Pegland.

Κάθε πολίτης έχει και μια ορισμένη ταχύτητα ποδηλασίας. Σε ένα ζευγάρι, θα χειρίζεται πάντα το ποδήλατο το πιο γρήγορο άτομο ενώ το πιο αργό άτομο απλά θα απολαμβάνει τη βόλτα. Με άλλα λόγια, αν τα μέλη ενός ζεύγους έχουν ταχύτητες ~a~ και ~b~, τότε η ταχύτητα ποδηλάτου του ζεύγους είναι ~max(a,\;b)~. Η συνολική ταχύτητα είναι το άθροισμα των ~N~ ατομικών ταχυτήτων των ποδηλάτων.

Για αυτό το πρόβλημα, σε κάθε αρχείο ελέγχου, θα σας ζητηθεί να απαντήσετε σε μία από τις δύο ερωτήσεις:

• Ερώτηση ~1~: Ποια είναι η ελάχιστη συνολική ταχύτητα, από όλες τις πιθανές αναθέσεις ανά ζεύγη;
• Ερώτηση ~2~: Ποια είναι η μέγιστη συνολική ταχύτητα, από όλες τις πιθανές αναθέσεις ανά ζεύγη;

Είσοδος

Η πρώτη γραμμή θα περιέχει τον τύπο της ερώτησης που πρέπει να απαντήσετε, ο οποίος είναι είτε ~1~ είτε ~2~.

Η δεύτερη γραμμή περιέχει τον ~N\;(1 \le N \le 100)~.

Η τρίτη γραμμή περιέχει ~N~ ακέραιους αριθμούς χωρισμένους με κενό διάστημα: τις ταχύτητες των πολιτών του Dmojistan.

Η τέταρτη γραμμή περιέχει ~N~ ακέραιους αριθμούς χωρισμένους με κενό διάστημα: τις ταχύτητες των πολιτών του Pegland.

Η ταχύτητα κάθε ατόμου θα είναι ένας ακέραιος αριθμός μεταξύ ~1~ και ~1000000~.

Για ~8~ από τους ~15~ διαθέσιμους βαθμούς θα τεθούν ερωτήσεις του τύπου 1. Για ~7~ από τους ~15~ διαθέσιμους βαθμούς, θα τεθούν ερωτήσεις τύπου ~2~.

Έξοδος

Εξάγετε τη μέγιστη ή την ελάχιστη συνολική ταχύτητα βάση της ερώτησης που τέθηκε.

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

input

1
3
5 1 4
6 2 4

output

12

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

Υπάρχει μια μοναδική βέλτιστη λύση:

• Συνδυάστε τον πολίτη από το Dmojistan με ταχύτητα ~5~ με τον πολίτη από την Pegland με ταχύτητα ~6~.
• Συνδυάστε τον πολίτη από το Dmojistan με ταχύτητα ~1~ με τον πολίτη από την Pegland με ταχύτητα ~2~.
• Συνδυάστε τον πολίτη από το Dmojistan με ταχύτητα ~4~ με τον πολίτη από την Pegland με ταχύτητα ~4~.

input

2
3
5 1 4
6 2 4

output

15

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

Υπάρχουν πολλαπλές πιθανές βέλτιστες λύσεις. Παρακάτω παρουσιάζεται μια βέλτιστη λύση:

• Συνδυάστε τον πολίτη από το Dmojistan με ταχύτητα ~5~ και τον πολίτη από την Pegland με ταχύτητα ~2~.
• Συνδυάστε τον πολίτη από το Dmojistan με ταχύτητα ~1~ και τον πολίτη από την Pegland με ταχύτητα ~6~.
• Συνδυάστε τον πολίτη από το Dmojistan με ταχύτητα ~4~ και τον πολίτη από την Pegland με ταχύτητα ~4~.

input

2
5
202 177 189 589 102
17 78 1 496 540

output

2016

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

Υπάρχουν πολλαπλές πιθανές βέλτιστες λύσεις. Παρακάτω παρουσιάζεται μια βέλτιστη λύση:

• Συνδυάστε τον πολίτη από το Dmojistan με ταχύτητα ~202~ με τον πολίτη από την Pegland με ταχύτητα ~1~.
• Συνδυάστε τον πολίτη από το Dmojistan με ταχύτητα ~177~ με τον πολίτη από την Pegland με ταχύτητα ~540~.
• Συνδυάστε τον πολίτη από το Dmojistan με ταχύτητα ~189~ με τον πολίτη από την Pegland με ταχύτητα ~17~.
• Συνδυάστε τον πολίτη από το Dmojistan με ταχύτητα ~589~ με τον πολίτη από την Pegland με ταχύτητα ~78~.
• Συνδυάστε τον πολίτη από το Dmojistan με ταχύτητα ~102~ με τον πολίτη από την Pegland με ταχύτητα ~496~.

Αυτό το άθροισμα δίνει ~202~ ~+~ ~540~ ~+~ ~189~ ~+~ ~589~ ~+~ ~496 = 2016~.