SPOJ in Armenian

Մնացորդային խաղը խաղալու համար նախ անհրաժեշտ է ընտրել  թիվ: Այնուհետև ընտրվում է երկու հաջորդականություն  a_i և b_i: Վերջում ընտրվում է s₀ սկզբնական թիվը: Խաղի նպատակն է s₀-ից հասնել 0-ին, որքան հնարավոր է քիչ քայլերի քանակով: Ամեն քայլում ընտրվում է i ինդեքս, ընթացիկ թիվը բազմապատկվում է a_i-ով, ավելացվում է b_i և վերցվում է m-ի վրա մնացորդը հետևյալ կերպ՝ s_j = (s_j-1*a_i+b_i) mod m

Մուտքը

Մուտքային ֆայլի առաջին տողում գրված է երեք թիվ՝ 0 < m <= 1000000, 0 <= n <= 10 և 0 < s₀ < m: Հաջորդ n տեղերից յուրաքանչյուրը պարունակում է 0 <= a_i <= 1000000000 , 0 <= b_i <= 1000000000 թվերի զույգը:

Ելքը

Ելքային ֆայլում անհրաժեշտ է արտածել մեկ ամբողջ թիվ՝ s₀-ից 0 հասնելու համար անհրաժեշտ մինիմալ քայլերի քանակը: Եթե հնարավոր չէ հասնել 0-ին՝ արտածել -1:

Օրինակ

Մուտքը.
5 2 1

3 1

2 1

Ելքը.
2