24364번 - ТОПЧЕТА 다국어

Митко играе следната игра. Той разполага с купчина от червени и сини топчета. В N кутии, номерирани с числата от 1 до N са поставени определен брой топчета с различни цветове (във всяка кутия има топчета от само един цвят – червени или сини). Митко си записва броя на топчетата във всяка кутия така: ако топчетата в кутията са сини, пред броя им слага знак „минус“, т.е. броят става отрицателно число. В началото на играта се пресмята сумата от числата, които е записал. След това Митко поставя в кутия с номер 1 толкова на брой топчета, колкото е разликата на общия брой и броя, който е в кутията. Ако се получи отрицателно число, в съответната кутия Митко поставя само сини топчета, а ако се получи положително - поставя червени топчета. Същото действие извършва с всички останали кутии. На втората стъпка се събира полученият нов брой на топчета във всички кутии и Митко трябва отново да започне да поставя в кутиите този брой минус броя, който се съдържа в съответната кутия. И така, тези действия се повтарят K пъти. Накрая Митко трябва да отговори на въпроса: Колко е разликата между максималния и минималния брой на топчета в кутиите след K на брой стъпки? Напишете програма balls, която пресмята тази разлика при зададени N, K и първоначален брой топчета във всяка кутия.

От първия ред на стандартния вход се въвеждат две цели числа N и K. От следващия ред се въвеждат N цели числа – брой на топките в кутиите. Ако топките са сини, числото е отрицателно, ако са червени – положително. Числата са разделени с по един интервал.

На един ред на стандартния изход програмата трябва да изведе едно цяло число – търсената разлика.

• 2 ≤ N ≤ 1000000
• 1 ≤ K ≤ 1000
• Числата в редицата имат стойности в интервал от -2000 000 000 до 2000 000 000

• В първата кутия има 7 сини топчета, във втората 1 червено, а в третата 3 сини.
• На първата стъпка (K=1) Митко ще получи сбор -9.
• В първата кутия ще остави 2 броя сини топчета: -9-(-7) = -2
• Във втората кутия ще постави 10 броя сини топчета, а ще махне червеното: -9-1= -10
• В третата кутия ще постави още 3 броя сини топчета, за да станат 6: -9-(-3) = -6
• На втората стъпка (K=2) Митко ще получи сбор -18.
• В първата кутия ще станат 16 броя сини топчета: -18-(-2) = -16
• Във втората кутия ще станат 8 броя сини топчета: -18+10= -8
• В третата кутия ще станат 12 броя сини топчета: -18+6 = -12

Най-големият брой топчета е в първата кутия – 16, най-малкият е 8 – във втората кутия. Разликата е 8.