(k-шы жұп) Сізге $n$ бүтін $a_1$, $a_2$, ..., $a_n$ сандардан тұратын $a$ массиві берілген.
Массивтің $(i, j)$ $1 \le i < j \le n$ индекстері арқылы $a_i$, $a_j$ жұбын ала аламыз және ол жұптың күші $a_i + a_j$ болады. Берілген массивтегі алуға болатын жұптардың барлығын күші бойынша \textbf{кемімейтін} ретпен сұрыптаған кездегі $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} ретпен тұрады және осындағы 3-шісі 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} ретпен тұрады және осындағы 7-шісі 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 \ge d$ болса, Елібай $X$ теңге төлейді, ал егер $X < d$ болса, $X + (d - X)^2$ теңге төлейді.
Елібай $i$ деген нөмірдегі объектіні қарап келу үшін такси шақырады (бас кеңседен объектіге дейінгі жолдың және кері жолдың ұзындығы бірге $d_i$ шақырымды құрайды). Ол бір рет такси шақырған кезде промо-кодты екі рет қолдана алмайды және келесі объектіге бару үшін қайтадан такси шақырады.
Айсұлтан Елібайдың досы болғандықтан, ол Елібайға $X$ санын таңдауға мүмкіндік берді. Әрине, $X$ теріс емес бүтін сан болуы керек. Сіздің тапсырмаңыз — Елібай ақшасын мейлінше аз жарататындай $X$ санын таңдауға көмектесу.

Кіріс деректер форматы:

Бірінші қатарда бір $N$ саны берілген.
Екінші қатарда бос орын арқылы $d_1, d_2, \ldots d_n$ бүтін сандары берілген — олар бас кеңседен кезекті объектіге дейінгі барып қайтқандағы жолдың ара қашықтығын көрсетеді.

Шығыс деректер форматы:

Бір сан шығарыңыз — егер Елібай $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$.
  

(Темірлан vs Рамазан) Тақтада $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.Мысал:

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$ типті бір, жалпы екі қорап $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$ типтері сәйкесінше бес қорап береді.
Төртінші мысалда Елдан екі қаламды алатындай ешқандай тәсілмен қораптарды таңдай алмайды.

Бағалау:

Есеп 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$)
Yшінші жолда $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)$