Obres V78601

Les reformes al pis del professor Oak duren més que l’obra de la Seu. En part, perquè el que es construeix un dia es pot destruir l’endemà. Intrigat per aquest fenomen, el professor ha mesurat les millores de cada dia, i se n’ha adonat que tenen forma cíclica.

Si mesurem amb “punts” l’estat del pis, i suposant que inicialment (dia 0) té 0 punts, podria passar que el cicle sigui de mida quatre: el primer dia el pis guanya 10 punts, l’endemà en perd 3, l’endemà en guanya 2, l’endemà en perd 5, i i el cicle ($+10$, $-3$, $+2$, $-5$) torna a començar per sempre. L’evolució dels punts del pis en aquest cas seria 0, 10, 7, 9, 4, 14, 11, 13, 8, 18, 15, 17, 12, …

Suposant que es faran obres sense parar, a partir de quin dia el pis mai baixarà de $p$ punts? Amb l’exemple anterior amb $p = 11$, la resposta seria 9, corresponent al dia amb 18 punts.

Entrada

L’entrada consisteix en diversos casos, cadascun amb $p$, la mida del cicle $n$, i els $n$ valors del cicle. Podeu suposar $1 \le p \le 10^8$, $1 \le n \le 10^5$, que tots els valors del cicle es troben entre $-10^5$ i $10^5$, i que la suma d’aquests valors és estrictament positiva.

Sortida

Per a cada cas, escriviu el primer dia a partir del qual l’estat del pis mai baixarà dels $p$ punts.

Puntuació

• Cas A:

  Casos on tant $n$ com la resposta són com a molt 100, com els de l’exemple d’entrada 1.

• Cas B:

  Casos on $n$ és com a molt 1000.

• Cas C:

  Casos de tot tipus.