Մնացորդի խաղ

Եկեք խաղ խաղանք. Պատկերացրեք, որ ունեք նախնական թիվ $s_0$ և երկու շարքեր $a_1, a_2, ..., a_n$, $b_1, b_2, ..., b_n$։ Ձեր նպատակը $s_0$-ից όσο հնարավոր է շուտ հասնել 0-ի։ Յուրաքանչյուր քայլին թույլատրվում է ընտրել ինդեքս i և կիրառել հետևյալ գործողությունը ընթացիկ թվի վրա.

Այս կերպ կարելի է ստանալ հաջորդ թիվը։ Պետք է որոշել, թե նվազագույն քանի քայլով հնարավոր է $s_0$-ից հասնել 0-ի։

Մուտք

Մուտքի առաջին տողում տրված են 3 ամբողջ թիվ՝ n, m և $s_0$ (0 ≤ n ≤ 10, 0 ≤ m ≤ 100000, և 0 < $s_0$ < m)։

Հաջորդ n տողերում տրված է երկուական թվերի զույգ $a_i, b_i$ (0 ≤ $a_i$, $b_i$ ≤ $10^9$)։

Ելք

Ծրագիրը պետք է տպի նվազագույն քայլերի քանակը, որով կարելի է $s_0$-ից հասնել 0-ի։ Եթե 0-ի ստացումը անհնար է, ծրագիրը պետք է տպի Impossible։

Օրինակներ