(k-я пара) Вам задан массив $a$, состоящий из $n$ целых чисел $a_1$, $a_2$, ..., $a_n$.
Два элемента массива $a_i$, $a_j$ с индексами $(i, j)$ $1 \le i < j \le n$, могут образовать пару и силой этой пары назовем $a_i + a_j$. Найдите силу пары, являющейся $k$-й по счету, если отсортировать все пары по неубыванию силы.

Формат входных данных:

В первой строке заданы два целых числа $n$ и $k$ ($1 \le k \le \frac{n * (n - 1)}{2}$).
Во второй строке через пробел заданы целые числа $a_1$, $a_2$, ..., $a_n$ ($0 \le a_i \le 10^6$).

Формат выходных данных:

Выведите ответ на задачу.

Примеры:

1.Вход:

3 3
7 1 4

Ответ:

11

2.Вход:

5 7
1 5 3 5 3

Ответ:

8

3.Вход:

10 32
0 0 0 0 0 0 0 0 0 0

Ответ:

0

4.Вход:

9 15
5 6 3 0 0 4 1 4 1

Ответ:

5

Замечание:

В первом примере можно сделать три пары с силами {$a_1$ + $a_2$, $a_1$ + $a_3$, $a_2$ + $a_3$} = {7 + 1, 7 + 4, 1 + 4} = {8, 11, 5}. Если их отсортировать по неубыванию силы, то получится {5, 8, 11} и третий элемент это 11.
Во втором примере можно сделать десять пар с силами {$a_1$ + $a_2$, $a_1$ + $a_3$, $a_1$ + $a_4$, $a_1$ + $a_5$, $a_2$ + $a_3$, $a_2$ + $a_4$, $a_2$ + $a_5$, $a_3$ + $a_4$, $a_3$ + $a_5$, $a_4$ + $a_5$} = {1 + 5, 1 + 3, 1 + 5, 1 + 3, 5 + 3, 5 + 5, 5 + 3, 3 + 5, 3 + 3, 5 + 3} = {6, 4, 6, 4, 8, 10, 8, 8, 6, 8}. Если их отсортировать по неубыванию силы, то получится {4, 4, 6, 6, 6, 8, 8, 8, 8, 10} и седьмой элемент это 8.

Система оценки:

Задача содержит 50 тестов, каждая из которых весят 2 балла.
Ограничения которые присутствуют в тестах:

• 10 тестов: $2 \le n \le 10^3$
  
• 20 тестов: $2 \le n \le 10^4$
  
• 20 тестов: $2 \le n \le 10^5$
  

(Такси) В городе Алматы проживает преуспевающий бизнесмен по имени Елибай. С недавних пор он занимается строительством $N$ объектов . Он каждый день ездит на своем автомобиле с головного офиса в объекты, осматривает объекты и возвращается обратно в офис. Он обязательно должен возвращаться в офис между походами в объекты, так как он должен заполнить некоторые документы. Сегодня у него случилась беда, у машины разрядился аккумулятор. Чтобы не опоздать он обратился к двум сервиса для заказа такси ZhureBER и Zhett. Тарифы у них оказались недешевыми. За $d$ километров придется платить $d^2$ тенге. Однако его друг Айсултан - который владеет сервисом такси предложил ему купить $N$ промо-кодов для поездки на такси со стоимостью $X$, тогда ему придется платить за каждую поездку $X$ тенге если $X \ge d$, иначе $X + (d - X)^2$ тенге.
Елибай для осмотра объекта под номером $i$ заказывает такси из офиса в объект и обратно (суммарная дистанция из офиса в объект и обратно $d_i$). Он не может за одну поездку два раза пользоваться промо-кодом и для осмотра нового объекта каждый раз заказывает новый такси.
Так как Айсултан давний друг Елибая, он предложил ему самому выбрать число $X$, конечно же $X$ должно быть неотрицательным целым числом.

Формат входных данных:

Первая строка входного файла будет содержать одно число $N$ — количество объектов с которыми занимается бизнесмен.
Во второй строке записаны $N$ целых чисел $d_1, d_2, \ldots d_n$ расстояние от офиса до $i$-го объекта и обратно.

Формат выходных данных:

Выведите одно целое число - минимальную суммарную количество денег Елибай должен заплатить если выберет число $X$ оптимально.

Примеры:

1.Вход:

5
7 7 7 7 7

Ответ:

35

2.Вход:

10
2 1 3 6 7 5 9 2 2 4

Ответ:

70

3.Вход:

2
0 100

Ответ:

199

Замечание:

Второй пример:
Если X = 6, мы можем получить минимальную стоимость 70.
Суммарно $6 \times 10 + {(9 - 6)}^2 + {(7 - 6)}^2 = 60 + 9 + 1 = 70$
Если X = 5, общая стоимость была бы 71. Если X = 7, общая стоимость была бы 74.

Система оценки:

Задача содержит 50 тестов, каждая из которых весят 2 балла.
Ограничения которые присутствуют в тестах:

• 4 теста: $1 \le N \le 2000$, $0 \le d_i \le 1000$. В добавок, расстояние до всех объектов одинаково. ($d_i = d_1$ для $i > 1$)
  
• 11 тестов: $1 \le N \le 2000$, $0 \le d_i \le 1000$
  
• 11 тестов: $1 \le N \le 2000$, $0 \le d_i \le 10^6$.
  
• 24 тестов: $1 \le N \le 200000$, $0 \le d_i \le 10^6$.
  

(Тима и Рама) На доске в ряд написано $N$ целых чисел. Темірлан и Рамазан играют в следующую игру:

• Они будут ходить по очереди, первым начинает Темірлан.
  
• На каждом ходу игрок может стереть с доски любое ненулевое количество чисел с начала, или с конца. Но нельзя стереть все числа.
  
• Игра закончится, когда на доске останется ровно одно число. Темірлан хочет минимизировать последнее число, а Рамазан хочет максимизировать это число.
  

Пока Темірлан отошел, Рамазан хочет стереть ровна $K$ чисел. Он может стереть любые числа. Когда Темірлан вернется, они начнут играть как обычно, но на доске будет написано $N-K$ чисел.
Для каждого из $Q$ чисел $K_1,K_2, ..., K_Q$, Рамазан хочет узнать, какое значение у последнего оставшегося числа, если он заранее сотрет $K_i$ чисел, и оба игрока играют оптимально?

Формат входных данных:

В первой строке находится одно целое число $N$.
Во второй строке находятся $N$ целых числа $A_1,A_2,...,A_N (1 \le A_i \le 10^6)$ --- числа написанные на доске.
В третьей строке находится одно целое число $Q$.
В четвертой строке находятся $Q$ целых числа $K_1,K_2,...,K_Q(0 \le K_i \le N - 1)$.

Формат выходных данных:

Выведите через пробел $Q$ чисел, $i$-е из них, значения последнего оставшегося числа, если Рамазан заранее сотрет $K_i$ чисел.

Примеры:

1.Вход:

4
1 4 2 3
4
0 1 2 3

Ответ:

1 3 3 4

2.Вход:

3
5 5 5
3
0 1 2

Ответ:

5 5 5

3.Вход:

6
2 7 5 4 8 10
3
3 5 2

Ответ:

7 10 7

Замечание:

В первом тесте при $K=3$, Рамазану выгодно стереть первое,второе и четвертое числа.

Система оценки:

Задача содержит 50 тестов, каждая из которых весят 2 балла.
Ограничения которые присутствуют в тестах:

• 3 теста: Первые три теста является тестами из примеров
  
• 5 тестов: $1 \le N \le 3, Q = 1, K_1 = 0$
  
• 10 тестов: $1 \le N \le 100, Q = 1, K_1 = 0$
  
• 12 тестов: $1 \le N \le 10^5, 1\le Q \le 2, 0 \le K_i \le 1$
  
• 10 тестов: $1 \le N \le 10^5, 1 \le Q \le 10^5,0 \le K_i \le N - 1$
  
• 10 тестов: $1 \le N \le 10^6, 1 \le Q \le 10^6, 0 \le K_i \le N - 1$
  

(Склад ручек) Елдан работает охранником на складе с ручками. Все ручки на складе хранятся в запакованных коробках. Елдан заметил, что всего есть $n$ типов коробок, в коробке типа $i$ лежит $a_i$ ручек и на складе коробок каждого типа очень много (больше $10^{12}$). Скоро должен приехать грузовик, чтобы забрать $s$ ручек в магазин. Елдану не сообщили, сколько ручек требуется в магазине, но он знает, что это значение не больше $x$. Поэтому он хочет подготовить минимальное количество коробок, чтобы мог отдать любое количество ручек от $1$ до $x$, не открывая коробок. Помогите Елдану посчитать, какое минимальное количество коробок ему нужно подготовить, либо сообщите, что это невозможно.

Формат входных данных:

В первой строке входных данных задано одно число $n$. Во второй строке заданы через пробел $n$ различных чисел $a_1, a_2, \dots, a_n$. В третьей строке задано одно число $x$. Все числе во входных данных являются целыми положительными.

Формат выходных данных:

Выведите ответ на задачу, если ответа не существует выведите $-1$.

Примеры:

1.Вход:

2
2 1
3

Ответ:

2

2.Вход:

1
1
1

Ответ:

1

3.Вход:

4
5 2 1 3
15

Ответ:

5

4.Вход:

2
5 3
2

Ответ:

-1

Замечание:

В первом примере Елдан может подготовить коробки с типами ${a_1, a_2}$.
При $s = 1$ он отдаст одну коробку $a_2$.
При $s = 2$ он отдаст одну коробку $a_1$.
При $s = 3$ он отдаст две коробки $a_1, a_2$ (2 + 1 = 3).
Во втором примере Елдан подготовит одну коробку ${a_1}$.
В третьем примере Елдан может подготовить коробки с типами ${a_1, a_1, a_2, a_2, a_3}$.
При $s = 1$ он отдаст коробку $a_3$.
При $s = 2$ он отдаст коробку $a_2$.
При $s = 3$ он отдаст коробки $a_2, a_3$.
При $s = 4$ он отдаст коробки $a_2, a_2$.
При $s = 5$ он отдаст коробки $a_2, a_2, a_3$.
При $s = 6$ он отдаст коробки $a_1, a_3$.
При $s = 7$ он отдаст коробки $a_1, a_2$.
При $s = 8$ он отдаст коробки $a_1, a_2, a_3$.
При $s = 9$ он отдаст коробки $a_1, a_2, a_2$.
При $s = 10$ он отдаст коробки $a_1, a_1$.
При $s = 11$ он отдаст коробки $a_1, a_1, a_3$.
При $s = 12$ он отдаст коробки $a_1, a_1, a_2$.
При $s = 13$ он отдаст коробки $a_1, a_1, a_2, a_3$.
При $s = 14$ он отдаст коробки $a_1, a_1, a_2, a_2$.
При $s = 15$ он отдаст коробки $a_1, a_1, a_2, a_2, a_3$.
Обратите внимание, что в данном тесте есть и другие варианты выбрать коробки, например ${a_1, a_1, a_3, a_3, a_4}$.
В четвертом примере Елдан не может выбрать какие-либо коробки, чтобы отдать две ручки.

Система оценки:

Задача содержит 50 тестов, каждая из которых весят 2 балла.
Ограничения которые присутствуют в тестах:

• 4 теста: $n = 1$, $a_i \le 25, x \le 25$
  
• 6 тестов: $n \le 3$, $a_i \le 25, x \le 25$
  
• 6 тестов: $n \le 5$, $a_i \le 25, x \le 25$
  
• 14 тестов: $n \le 10^5, a_i \le 10^5, x \le 10^5$
  
• 20 тестов: $n \le 10^5, a_i \le 10^{12}, x \le 10^{12}$
  

(Опять деревья) Дается неориентированное дерево из $n$ вершин, определим расстояние между двумя вершинами как количество ребер в их кратчайшем пути. Диаметром дерева является максимальное расстояние среди всех пар вершин в дереве.
В данной задаче вам нужно минимизировать диаметр дерева применив не более $k$ операций удаления.
Операция удаления представляет собой удаление вершины и всех ребер смежных с ней, при этом не разрешается удалять вершину если после операции граф станет безсвязным.

Формат входных данных:

В первой строке содержатся числа $n$ и $k$ ($0 \le k \le n - 1$) - количество вершин и максимальное количество вершин которое можно удалить.
В следующих $n-1$ строках следует описание графа.
В каждой строке содержатся числа $u$ и $v$ ($1 \le u, v \le n$) - означает что существует неориентированное ребро между вершиной $u$ и вершиной $v$.

Формат выходных данных:

Выведите ровно одно число - минимальный диаметр который можно получить удалив не более $k$ вершин.

Примеры:

1.Вход:

5 2
1 4
3 2
1 2
5 2

Ответ:

2

2.Вход:

14 5
13 2
10 4
6 12
8 11
11 13
5 14
10 3
11 5
12 1
9 7
11 10
10 9
6 10

Ответ:

3

Система оценки:

Задача содержит 100 тестов, каждая из которых весят 1 балл.
Ограничения которые присутствуют в тестах:

• 10 теста: $n \le 20$
  
• 10 тестов: $n \le 100$
  
• 5 тестов: $k = 0$
  
• 24 тестов: $n \le 2000$
  
• 51 тестов: $n \le 5000$
  

(Башни) У Алана есть $n$ башен, у каждой из которых есть параметр $a_i$ - числитель рук и параметр $b_i$ - знаменатель рук. В $q$ очень легких делах, которых он задумал, ему нужно определить руки у башен. Для этого, каждой башне он может сказать сделать целое количество рук - $[\frac{a_i}{b_i}]$ или дробное количество рук - $\frac{a_i}{b_i}$. Для $i$-го дела, которые он задумал, Алану необходимо суммарно ровно $x_i$ рук. Для каждого из этих дел Алан берет все $n$ башен, то есть суммарная \textit{рукость} всех башен должна равняться $x_i$. Помогите Алану найти количество способов сделать это, для каждого из $q$ легких дел.

Формат входных данных:

В первой строке дается целое положительное число $n$ ($1 \le n \le 40$).
Во второй строке дается $n$ целых положительных чисел $a_1, a_2, .., a_n$ ($1 \le a_i \le 100000$)
В третьей строке дается $n$ целых положительных чисел $b_1, b_2, .., b_n$ ($1 \le b_i \le 100000$)
В следующей дается целое положительное число $q$ ($1 \le q \le 100000$) - количество запросов.
В следующих $q$ строках находится по одному целому числу $x$ - запросы из условия ($1 \le x \le 4000000$)

Формат выходных данных:

Выведите $q$ целых числе по одному в каждой строке - количество способов получить ровно $x_i$ целых рук.

Примеры:

1.Вход:

5
14 10 12 6 15
8 8 9 9 15
4
4
5
6
7

Ответ:

2
4
2
0

2.Вход:

3
6 2 8
8 8 4
2
2
3

Ответ:

2
2

Система оценки:

Задача содержит 100 тестов, каждая из которых весят 1 баллов.
Ограничения которые присутствуют в тестах:

• 20 теста: $(1 \le n \le 10, 1 \le q \le 5)$
  
• 31 тестов: $(1 \le n,q \le 20)$
  
• 49 тестов: $(1 \le n \le 40, 1 \le q \le 10^5)$