h2. Date de ieşire

Fişierul de ieşire $referat.out$ va contine $T$ linii cu exact un numar natural, reprezentand numarul de pozitii in care poate sa fie introdus noul cuvant astfel incat baietii sa obtina cel putin un rand in plus pentru testul respectiv.

Fişierul de ieşire $referat.out$ va contine un singur numar natural reprezentand numarul de pozitii in care poate sa fie introdus noul cuvant astfel incat baietii sa obtina cel putin un rand in plus.

h2. Restricţii
* $1 ≤ N ≤ 100.000$
* $1 ≤ T ≤ 10$
* $1 ≤ P,S{~i~} ≤ L ≤ 1.000.000.000$

* Pentru $30%$ din teste $N ≤ 1000$

h2. Exemplu

7 1 5 2 8
4
|3

|

|

h2. Explicatii
 
Copii au $5$ cuvinte de lungime $7, 1, 5, 2, 8$, sa zicem urmatoarele cuvinte: $Sambata$ $A$ $Venit$ $Cu$ $Beatrice$, iar cuvantul pe care vrem sa-l introducem este $Rece$.
Initial textul pus pe linii de lugime maxim $10$ este:
 
$SambataA$
$VenitCu$
$Beatrice$
 
In functie de unde introducem cuvantul $Rece$ se obtin urmatoarele distribuiri pe linii:
 
$Rece$
$SambataA$
$VenitCu$
$Beatrice$
 
$Sambata$
$ReceAVenit$
$CuBeatrice$
 
$SambataA$
$ReceVenit$
$CuBeatrice$
 
$SambataA$
$VenitRece$
$CuBeatrice$
 
$SambataA$
$VenitCu$
$Rece$
$Beatrice$
 
si
 
$SambataA$
$VenitCu$
$Beatrice$
$Rece$
 
Observam ca doar daca introducem cuvantul $Rece$ la inceput, fix inainte de cuvantul $Beatrice$, si la final numarul de linii creste cu 1. Astfel raspunsul este 3.

== include(page="template/taskfooter" task_id="referat") ==