Masala E

N ta sondan tashkil topgan A massivi berilgan. Massivning - bahosi massivning ikki qo'shni elementlari farqining maksimali hisoblanadi. Massivning ko'pi bilan M ta elementi qiymatini o'zgartirgan holda, uning bahosini minimallashtiring.

Birinchi qatorda N va M butun sonlari kiritiladi.

Keyingi qatorda N ta butun son - A massiv elementlari kiritiladi.

$1 \le N, M \le 2000$

$1 \le i \le N$ uchun $-10^9 \le A_i \le 10^9$

Yagona butun son, massivning ko'pi bilan M ta elementi qiymatini o'zgartirgan holda, uning bahosini mumkin bo'lgan minimal qiymatini chop eting.