Алиса мен Бобқа ұзындығы $N$ болатын бүтін сандардан тұратын $A$ массиві берілген.

Алиса дәл $K$ бірліктен тұратын ұзындығы $N$ болатын $B$ екілік жолын таңдайды және бұл жол бүкіл ойын бойы өзгеріссіз қалады.

Кез келген сәтте $i$ индексі тек $B_i = 1$ болғанда ғана қорғалған болады, ал Боб $i$ индексін тек $B_i = 0$ болғанда ғана таңдай алады.

Боб нөл немесе одан да көп жүріс жасайды. Бобтың бастапқы ұпайы $0$-ге тең.

Бір жүрісте Боб келесі шарттарды қанағаттандыратын $i$ индексін таңдайды:

• $B_i = 0$;
• $1 \le i \le |A|$.

Боб ағымдағы $A_i$ мәнін өз ұпайына қосады және бұл элементті $A$ массивінен өшіреді. Әрбір өшіруден кейін $|A|$ мәні $1$-ге кемиді, ал $A$ массивінің қалған элементтері $1$-ден $|A|$-ға дейін қайта индекстеледі.

Сондықтан $B$ бекітілген элементтерге емес, ағымдағы индекс орындарына қолданылады. Жылжулардан кейін бір элементтің өзі қорғалған немесе өшірілетін болып өзгеруі мүмкін.

Егер Боб жүрістер барысында $P_1, P_2, \dots, P_m$ индекстерін таңдаса, олар өспейтін болуы керек, яғни:

$$P_1 \ge P_2 \ge \dots \ge P_m$$

Боб бір индексті бірнеше рет таңдай алады.

Алиса Бобтың ұпайын барынша азайтқысы келеді, ал Боб оны барынша көбейткісі келеді.

Екі ойыншы да тиімді ойнаған жағдайда Бобтың соңғы ұпайын табыңыз.

Кіріс деректер

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

T
N K
A1 A2 ... AN
...

Шектеулер

• Барлық кіріс мәндері бүтін сандар.
• $1 \le T \le 10^5$
• $1 \le N \le 6000$
• $0 \le K \le N$
• $-10^9 \le A_i \le 10^9$
• Барлық тест жағдайлары бойынша $N$ қосындысы $10^6$-нен аспайтынына кепілдік беріледі.
• Барлық тест жағдайлары бойынша $N^2$ қосындысы $6000^2$-тан аспайтынына кепілдік беріледі.

Шығыс деректер

Әрбір тест жағдайы үшін бір бүтін санды — Бобтың соңғы ұпайын шығарыңыз.

Мысал

Кіріс деректер 1

6
5 2
4 -1 7 -3 2
4 0
-5 -2 -1 -3
4 4
2 -7 5 1
1 0
-1
2 1
0 1
3 1
1 -1 1

Шығыс деректер 1

7
0
0
0
1
1

Ескертпе

• 1-тест жағдайы: Алиса $B = 10001$ жолын таңдай алады. Сонда бастапқыда Бобқа мәндері $-1$, $7$ және $-3$ болатын $2$, $3$ және $4$ индекстері қолжетімді болады. Боб $3$ индексін бір рет таңдау арқылы ($7$ мәнін қосып) $7$ ұпайға кепілдік бере алады. Осыдан кейін әрбір келесі таңдалатын индекс ең көбі $3$ болуы керек, сондықтан $4$ индексін таңдау мүмкін емес, ал кез келген одан арғы заңды жүріс оң емес мәнді қосады. Алиса Бобтың $7$-ден артық жинай алмауын мәжбүрлей алады, сондықтан жауап — $7$.
• 2-тест жағдайы: $K = 0$ болғандықтан, Алисада таңдау жоқ, $B = 0000$. Бобқа барлық индекстер қолжетімді, бірақ массивтегі әрбір мән теріс. Кез келген жүріс Бобтың ұпайын азайтады, сондықтан Бобтың тиімді ойыны — ешқандай жүріс жасамау. Демек, жауап — $0$.
• 3-тест жағдайы: $K = N$ болғандықтан, Алисада таңдау жоқ, $B = 1111$. Әрбір орын қорғалған, сондықтан Бобта мүлдем заңды жүріс жоқ. Осылайша, Бобтың ұпайы — $0$.