GR-H3. Kam to‘xtash

Mashina 0 nuqtadan T km uzoqlikdagi shaharga ketmoqda, 1 km ga 1 litr sarflaydi, bakida boshida F litr bor (bak hajmi cheksiz). Yo‘lda n ta shoxobcha bor: i-si xᵢ km da, unda fᵢ litr olish mumkin (hammasini). Shaharga yetish uchun eng kamida nechta shoxobchada to‘xtash kerak? Iloji bo‘lmasa — -1.

Kirish ma’lumotlari

Birinchi qatorda T, F, n. Keyingi n qatorda xᵢ fᵢ (xᵢ o‘sish tartibida).

Chiqish ma’lumotlari

Bitta son — to‘xtashlar soni yoki -1.

Cheklovlar

1 ≤ T, F ≤ 10⁹; 0 ≤ n ≤ 2·10⁵; 0 < x₁ < … < xₙ < T; 1 ≤ fᵢ ≤ 10⁹.