У Сережи есть m непустых множеств целых чисел A1, A2, ..., Am. По счастливой случайности оказалось, что данные множества являются разбиением множества всех целых чисел от 1 до n. Другими словами, для любого целого v (1 ≤ v ≤ n) существует ровно одно множество At такое, что 
. Кроме того у него есть целое число d.
Сережа решил выбрать несколько множеств из имеющихся. Предположим, что i1, i2, ..., ik (1 ≤ i1 < i2 < ... < ik ≤ m) — это индексы выбранных множеств. Тогда определим массив целых чисел b равный объединению выбранных множеств, то есть 
. Будем считать, что массив b отсортирован по возрастанию. Элемент с номером j в этом массиве (j-ый по возрастанию) будем обозначать bj. Сережа считает, что его выбор множеств правильный, если выполняются условия:
b1 ≤ d; bi + 1 - bi ≤ d (1 ≤ i < |b|); n - d + 1 ≤ b|b|.Сережа хочет найти k — минимальное количество выбранных множеств, чтобы его выбор был правильным. Помогите ему в этом.