microbuz

O companie de transport cu microbuze din județul Iași a adoptat o strategie proprie pentru rutele din județ:

• niciun traseu nu poate avea mai mult de $165$ kilometri
• distanța între două stații consecutive este de un kilometru
• un pasager poate pleca din orice stație şi poate să își cumpere bilete pentru parcurgerea a $1, 2, \dots, 10$ kilometri
• fiecare dintre cele zece distanţe posibile au bilete cu preţuri distincte

De exemplu:

Gigel, care călătoreşte cu microbuzul exact $N$ kilometri, poate să aleagă una sau mai multe distanţe dintre cele zece stabilite și să cumpere biletele corespunzătoare. Compania impune ca un pasager să poată cumpăra maxim $3$ bilete de același tip. Gigel observă că pentru aceeași sumă poate achiziționa seturi diferite de bilete cu prețuri distincte. Pentru exemplu de mai sus, cu $98$ de lei el poate cumpăra câte un bilet cu prețurile $11, 14, 29, 44$ lei sau câte un bilet cu prețurile $45, 53$ lei ($11+14+29+44 = 45+53$).

Cerință

Scrieţi un program care să rezolve următoarele cerințe:

1. determină preţul minim al unui set de bilete ce poate fi achiziționat pentru parcurgerea a exact $N$ kilometri;
2. determină distanţele alese de Gigel, astfel încât preţul total al călătoriei să fie minim;
3. determină două seturi distincte de bilete pentru care prețul total al biletelor este același și este cel mai mare posibil. Pentru fiecare set nu este permisă alegerea mai multor bilete cu același preț și nu există două bilete cu același preț în ambele seturi.

Date de intrare

Fișierul de intrare microbuz.in are trei linii. Pe prima linie se află un număr natural $C$ ce reprezintă cerința ($1, 2$ sau $3$). Linia a doua conține zece valori naturale ordonate strict crescător, separate prin câte un spaţiu, reprezentând preţurile pentru parcurgerea a $1, 2, \dots, 10$ kilometri. Linia a treia conţine valoarea $N$ reprezentând distanţa pe care doreşte să o parcurgă Gigel.

Date de ieșire

Fișierul de ieșire microbuz.out are următoarea structură:

• dacă $C = 1$, pe prima linie se va afișa un întreg reprezentând costul minim al călătoriei;
• dacă $C = 2$, pe fiecare linie se vor afișa câte două numere întregi, separate printr-un spaţiu, reprezentând distanța parcursă şi preţul biletului corespunzător;
• dacă $C = 3$, pe prima linie se va afișa prețul comun al celor două seturi de bilete, iar pe următoarele două linii câte un set de bilete dat prin numărul de km pentru biletele din set, în ordine strict crescătoare, separate prin câte un spațiu.

Restricții și precizări

• $C \in {1, 2, 3}$
• $1 \leq N \leq 165$;
• cele $10$ prețuri sunt numere naturale din intervalul [$10, 99$]
• răspunsul la cerința $3$ nu depinde de valoarea lui $N$
• Pentru $28$ de puncte, $C = 1$
• Pentru $38$ de puncte, $C = 2$
• Pentru $34$ de puncte, $C = 3$

Exemplul 1

microbuz.in

1
11 14 18 23 29 36 44 45 53 64
15

microbuz.out

86

Explicație

Cerința este $1$. Costul minim total este $86$.

Exemplul 2

microbuz.in

2
11 14 18 23 29 36 44 45 53 64
15

microbuz.out

3 18
4 23
8 45

Explicație

Cerința este $2$. Biletele cumpărate și prețurile lor sunt:

$3$ km parcurși, preț $18$
$4$ km parcurși, preț $23$
$8$ km parcurși, preț $45$

Exemplul 3

microbuz.in

2
13 17 18 19 21 22 25 28 31 37
39

microbuz.out

7 25
7 25
8 28
8 28
9 31

Explicație

Cerința este $2$. Biletele cumpărate și prețurile lor sunt:

$7$ km parcurși, preț $25$
$7$ km parcurși, preț $25$
$8$ km parcurși, preț $28$
$8$ km parcurși, preț $28$
$9$ km parcurși, preț $31$

Exemplul 4

microbuz.in

3
11 14 18 23 29 36 44 45 53 64
15

microbuz.out

163
2 3 4 7 10 
5 6 8 9

Explicație

Cerința este $3$. Prețul maxim comun este $163$.
Setul $1$: câte un bilet cu prețurile $14 \ 18 \ 23 \ 44 \ 64$.
Setul $2$: câte un bilet cu prețurile $29 \ 36 \ 45 \ 53$.