Fişierul intrare/ieşire:	lemans.in, lemans.out	Sursă	ONSEPI 2021, clasa a 9-a
Autor	Tulba-Lecu Gabriel	Adăugată de	Arhire Andrei •Andrei-27
Timp execuţie pe test	0.2 sec	Limită de memorie	32000 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Le Mans

Ne aflăm înainte de începutul faimoasei curse de anduranţă de la Le Mans. După cum bine stiţi, într-o cursă de anduranţă maşina care a parcurs cea mai mare distanţă pe parcursul cursei este considerată câştigătoare.

Anul acesta Federaţia Internaţională de Automobilism (FIA) a făcut câteva schimbări majore cu privire la desfăşurarea cursei. Anul acesta cursa va dura exact T secunde şi vor participa N echipe, fiecare echipă având câte o maşină, iar fiecare maşină poate pleca de pe oricare dintre cele M poziţii din grila de start.

De asemenea, FIA a impus câteva reguli care au nemulţumit echipele participante:

• Fiecare maşină este obligată sa se deplaseze cu o viteză constantă pe parcursul întregii curse. Astfel, a i-a maşină se va deplasa cu viteza de v[i] metri pe secundă.
• Dacă o maşină pleacă de pe o poziţie j din grila de start, aceasta se află la o distanţă de p[j] metri după linia de start, iar această distanţă este luată în considerare ca o distanţă deja parcursă în cadrul cursei.

Ca semn de protest asupra noului regulament, echipele au hotărât să se aşeze în grila de start astfel încât diferenţa maximă dintre distanţele parcurse de oricare două maşini să fie cât mai mică posibil.

Date de intrare

Pe prima linie din fişierul lemans.in se vor afla 3 numere:

• T - durata cursei exprimată în secunde,
• N - numărul de maşini,
• M - numărul de poziţii de start din grilă.

Pe a doua linie se află N numere separate prin câte un spaţiu, reprezentând şirul v de viteze ale maşinilor.

Pe a treia linie se află M numere separate prin câte un spaţiu, reprezentând şirul p - distanţele faţă de linia de start a poziţiilor de start din grilă.

Date de ieşire

Fişierul lemans.out va conţine pe prima linie un singur număr, reprezentând valoarea minimă posibilă a diferenţei maxime dintre distanţele parcurse de oricare două maşini.
Pe a doua linie se vor afla N numere între 1 şi M separate prin câte un spaţiu, al i-lea număr reprezentând poziţia de start din grilă a maşinii cu numărul i.

Restricţii

• 2 ≤ N, M ≤ 10³,
• 1 ≤ T ≤ 10³,
• 1 ≤ v[i] ≤ 10⁶, ∀ i ∈ {1, 2, ..., N},
• 0 ≤ p[i] ≤ 10⁹, ∀ i, j ∈ {1, 2, ..., M},
• Două sau mai multe maşini pot porni de pe aceeaşi poziţie din grila de start,
• În grilă pot exista şi poziţii neocupate de o maşină,
• Pot exista mai multe distribuţii ale maşinilor pe grila de start, ce oferă o soluţie optimă. Se acceptă orice soluţie corectă.
• Subtask 1 - 8 puncte - M = 1,
• Subtask 2 - 9 puncte - M = 2,
• Subtask 3 - 10 puncte - N, M ≤ 7,
• Subtask 4 - 19 puncte - v[i] ≤ 10³ şi p[i] ≤ 10⁶,
• Subtask 5 - 23 de puncte - N, M ≤ 100,
• Subtask 6 - 31 de puncte - nu există restricţii suplimentare.

Exemplu

Explicaţie

Distanţa minimă posibilă este 5 şi se poate obţine astfel:

• Maşina 1 pleacă de pe poziţia 3, deci va parcurge p [3] + v [1] · 5 = 11 + 2 · 5 = 21 metri;
• Maşina 2 pleacă de pe poziţia 1, deci va parcurge p [1] + v [2] · 5 = 7 + 3 · 5 = 22 metri;
• Maşina 3 pleacă de pe poziţia 2, deci va parcurge p [2] + v [3] · 5 = 1 + 4 · 5 = 21 metri;
• Maşina 4 pleacă de pe poziţia 2, deci va parcurge p [2] + v [4] · 5 = 1 + 5 · 5 = 26 metri.

Cum se trimit solutii?