У Потоколяндії всього є n різних видів ялинкових прикрас, пронумерованих цілими числами від 1 до n. Кількість прикрас i-го виду рівна a i
​
.
Дідусик Морозик зібрав усі прикраси Потоколяндії в одну купу і витягатиме з неї по одній прикрасі випадковим чином. Набір витягнутих прикрас Дідусик вважає новорічно-красивим, якщо з прикрас набору можна утворити хоча б k пар прикрас одного виду. Наприклад, використовуючи набір прикрас {1,2,1,2,1,1,3} (тут однаковими числами позначено прикраси одного виду) можна утворити не більше ніж три пари прикрас одного виду — дві пари прикрас виду 1 та одну пару прикрас виду 2.
До ть Морозику дізнатись мінімальну кількість витягань прикрас з купи, за якої гарантовано буде витягнуто новорічно-красивий набір прикрас. Гарантується, що якщо Дідусик витягне всі прикраси з купи, то він зможе утворити хоча б k пар прикрас одного виду.
Входные данные

Перший рядок містить два цілі числа n та k (1≤n,k≤10
5
).
Другий рядок містить n цілих чисел a
1
​
,a
2
​
,…,a
n
​
(1≤a
i
​
≤10
5
).
Выходные данные

Виведіть одне ціле число — відповідь на задачу.

1. 
var 
n,i,k,sum,g:integer;

begin
readln(n);
g:=n;
while n<>0 do begin
 g:= g div 10;
 k +=1;
end;

for i:=1 to k do begin
g:= n mod 10;
sum:= sum + g;
n:=n div 10;
end;
if sum> 10 then
writeln('верно')
else
('неверно');
end.

2.
var 
n,i,k,p,h,g:integer;

begin
readln(n);
g:=n;
while n<>0 do begin
 g:= g div 10;
 k +=1;
end;
p:=n mod 10;
n:=n div 10;
for i:=1 to k-1do begin
g:= n mod 10;
if g = p then
 h += 1;
n:=n div 10;
end;
writeln(h);
end.

3.
const
n=10;
var

a:array[1..n]of integer;
i,sum:integer;

begin
a[n]:=0;
for i:=1 to 9 do
readln(a[i]);

for i:=1 to n do 
 sum:=sum+a[i];
writeln(sum);
end.

4.
var

n:integer;

begin

readln(n);

while n<>0 do begin
n:=n div 10;
k += 1;
end;
if k = 4 then
writeln('число четырехзначное')
else
writeln('число не четырехзначное');
end.

5.
var

a:array[1..10]of integer;
i:byte;

begin

for i:=1 to 10 do
readln(a[i]);

for i:=1 to 10 do begin
 if a[i] = 2 then
writeln('да есть');
break;
end;
end.

В задаче имеется "топорное решение" — посчитать напрямую. Получившееся число будет восьмизначным, что не так уж и страшно, если в голову не приходят другие решения.

Рассмотрим, однако, решение, которое позволит делать подобные задачи без прямого подсчёта. Для этого, прежде всего, переведём всё в степени тройки:

98328316+35+35+35−9−32−32==
9
8
+
3
5
−9 =
3
2
8
+
3
5
−
3
2
=
3
16
+
3
5
−
3
2

Как представляется число 3n в троичной системе счисления? Давайте подумаем, как мы переводим из десятичной системы в троичную? Сначала делим на 3, затем частное делим на 3, затем новое частное на 3 и т.п. Что получится в случае деления 3n на 3? Очевидно, что 3n-1. А если его поделить дальше на 3, то получится 3n-2. Если так сделать n раз, то в конце останется 30, то есть. Таким образом, это будет число 100..00, где количество нулей равно n.

То есть, например, 8-ая степени тройки в троичной системе представима в виде 1000000003. А 35 — это 1000003.

Вернёмся теперь к нашей сумме. Давайте сначала в столбик сложим 316 и 35 в троичной системе счисления.

100…000000016100000100…0⏟10100000 1
00
…
0000000
⏞
16
100000 1
00
…
0
⏟
10
100000

Теперь остаётся из этого вычесть 32. Для этого придётся "занять" разряд. Но принцип тут такой же, как и в обычной, десятичной системе счисления, только 0 будут превращаться не в 9, а в 2 (самую большую цифру в троичной системе счисления:

100…0⏞10100000−100100…0⏟10022200 1
00
…
0
⏞
10
100000 −100 1
00
…
0
⏟
10
022200

Таким образом, количество двоек в указанной сумме получилось равным 3.

ответ: 3 двойки в троичной записи.