A. Өсдөг дараалал

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 64 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

$a_0$, $a_1$, ... , $a_{t-1}$ дарааллын хувьд $a_{i-1} < a_i$ ($0 < i < t$) бол өсдөг дараалал гэнэ.

Танд $b_0$, $b_1$, ... , $b_{n-1}$ ба $d$ тоо өгөгджээ. Үйлдэл бүрт $b$ дарааллын аль нэг тоог сонгон авч $d$ тоог нэмж болно. Хамгийн цөөндөө хэдэн үйлдлийн дараа өсдөг дараалал болгож болох вэ?

Оролт

Эхний мөрөнд $n$ ба $d$ тоо ($2 ≤ n ≤ 2000$, $1 ≤ d ≤ 10^6$). Дараагийн мөрөнд хоосон зайгаар тусгаарлагдсан $b_0$, $b_1$, ... , $b_{n-1}$ ($1 ≤ b_i ≤ 10^6$) тоонууд өгөгдөнө.

Гаралт

Өсдөг дараалал болгох хамгийн цөөн үйлдлийн тоо.

Орчуулсан: gmunkhbaatarmn

Жишээ тэстүүд

Оролт
4 2
1 3 3 2
Гаралт
3
Сэтгэгдлүүдийг ачааллаж байна...