У Сережи есть m непустых множеств целых чисел A₁, A₂, ..., A_m. По счастливой случайности оказалось, что данные множества являются разбиением множества всех целых чисел от 1 до n. Другими словами, для любого целого v (1 ≤ v ≤ n) существует ровно одно множество A_t такое, что . Кроме того у него есть целое число d.

Сережа решил выбрать несколько множеств из имеющихся. Предположим, что i₁, i₂, ..., i_k (1 ≤ i₁ < i₂ < ... < i_k ≤ m) — это индексы выбранных множеств. Тогда определим массив целых чисел b равный объединению выбранных множеств, то есть . Будем считать, что массив b отсортирован по возрастанию. Элемент с номером j в этом массиве (j-ый по возрастанию) будем обозначать b_j. Сережа считает, что его выбор множеств правильный, если выполняются условия:

Сережа хочет найти k — минимальное количество выбранных множеств, чтобы его выбор был правильным. Помогите ему в этом.