== include(page="template/taskheader" task_id="metrou3") ==

Problema aceasta este despre metroul din Cluj. Glumim, bineînţeles, nu există metrou în Cluj. E de fapt vorba de Zalău. Metroul din Zalău este un ciclu cu $N$ staţii, distanţa între două staţii consecutive nefiind constantă. Aceste distanţe vă sunt date prin şirul $D$: valorea $D[i]$ reprezintă durata parcurgerii distanţei dintre staţia $i$ şi staţia $(i + 1) modulo N$ în secunde. Fie $T$ durata unui tur complet al metroului (egală cu suma valorilor din $D$). Ştim că există doar două trenuri: unul care se va afla în staţia $0$ în secunda $A$, mergând în direcţia staţiei $1$ şi unul care se va afla în staţia $0$ în secunda $B$ şi merge în direcţia staţiei $N - 1$. Secundele $A$ şi $B$ sunt nişte momente *oarecare* în care trenurile se află în staţia $0$. Ele se vor afla în staţia $0$ şi în momentele $A + k * T$, respectiv $B + k * T$, pentru orice $k$ *întreg*. Cu alte cuvinte, trenurile au circulat dintotdeauna şi vor circula pentru totdeauna.

Problema aceasta este despre metroul din Cluj. Glumim, bineînţeles, nu există metrou în Cluj. E de fapt vorba de Zalău. Metroul din Zalău este un ciclu cu $N$ staţii, distanţa între două staţii consecutive nefiind constantă. Aceste distanţe vă sunt date prin şirul $D$: valorea $D[i]$ reprezintă durata parcurgerii distanţei dintre staţia $i$ şi staţia $(i + 1) modulo N$ în secunde. Fie $T$ durata unui tur complet al metroului (egală cu suma valorilor din $D). Ştim că există doar două trenuri: unul care se va afla în staţia $0$ în secunda $A$, mergând în direcţia staţiei $1$ şi unul care se va afla în staţia $0$ în secunda $B$ şi merge în direcţia staţiei $N - 1$. Secundele $A$ şi $B$ sunt nişte momente *oarecare* în care trenurile se află în staţia $0$. Ele se vor afla în staţia $0$ şi în momentele $A + k * T$, respectiv $B + k * T$, pentru orice $k$ *întreg*. Cu alte cuvinte, trenurile au circulat dintotdeauna şi vor circula pentru totdeauna.

Dorim să evaluăm eficienţa metroului din Zalău. În acest scop vom nota cu $getTime(Start, End, EntryTime)$ timpul minim necesar pentru a ajunge din staţia $Start$ în staţia $End$ dacă suntem pe peron la secunda $EntryTime$. Pentru a avea o imagine generală a experienţei călătorului obişnuit dorim să calculăm valoarea expresiei:
 
$Suma(getTime(Start, End, EntryTime), 0 ≤ Start ≤ N - 1, 0 ≤ End ≤ N - 1, 0 ≤ EntryTime ≤ T)$

Dorim să evaluăm eficienţa metroului din Zalău. În acest scop vom nota cu $getTime(Start, End, EntryTime)$ timpul minim necesar pentru a ajunge din staţia $Start$ în staţia $End$ dacă suntem pe peron la secunda $EntryTime$. Pentru a avea o imagine generală a experienţei călătorului obişnuit dorim să calculăm suma valorilor acestei funcţii pentru orice Start

h2. Date de intrare