Problema Alinieri

Se consideră modelul unui sistem solar format din N planete care se rotesc în jurul unei stele S, în sens trigonometric. Traiectoriile planetelor se consideră circulare și de raze diferite, iar vitezele de rotație ale planetelor în jurul stelei sunt numere naturale și sunt exprimate în grade pe zi (°/zi).

Cerință

Cunoscând numărul de planete N și vitezele lor de rotație Vi, 1 ≤ i ≤ N precum și două numere naturale P și Z, să se determine numărul A de alinieri a câte minimum P planete, pe o dreaptă ce trece prin centrul stelei S, după trecerea celor Z zile. Evoluția sistemului solar începe cu toate planetele așezate orizontal, în dreapta stelei S.

De exemplu, pentru n = 4, p = 3, z = 365, v = (20, 11, 8, 6), aliniearea a minimum 3 planete din cele 4 se va face la finalul zilelor 60, 90, 120, 180, 240, 270, 300, 360. După 365 de zile vor exista A = 8 alinieri.

Date de intrare

Fișierul de intrare alinieri.in conține pe prima linie, în această ordine, numerele naturale N, P și Z, iar pe-a doua linie, N numere naturale Vi, 1 ≤ i ≤ N cu semnificația de mai sus. Numerele aflate pe aceeași linie a fișierului sunt separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire alinieri.out va conține pe prima linie numărul A, cu semnificația de mai sus.

Restricții și precizări

• 2 ≤ P ≤ N ≤ 105
• 1 ≤ Z ≤ 106
• 1 ≤ Vi ≤ 103, 1 ≤ i ≤ N
• Pentru teste în valoare de aproximativ 33% din punctajul total 1 ≤ Z ≤ 1000
• Pentru teste în valoare de aproximativ 33% din punctajul total 1 ≤ N ≤ 100
• Pentru teste în valoare de aproximativ 33% din punctajul total 2 ≤ P ≤ 9
• Se vor lua în considerare doar alinierile de la sfârșitul fiecărei zile (ora 24:00), când planetele și-au încheiat parcursul zilnic.

Exemple