לאליס ולבוב נתון מערך של מספרים שלמים $A$ באורך $N$.

אליס בוחרת מחרוזת בינארית $B$ באורך $N$ עם בדיוק $K$ אחדות, ומחרוזת זו קבועה לכל אורך המשחק.

בכל רגע, אינדקס $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$. אז, בהתחלה, האינדקסים הזמינים לבוב הם $2$, $3$ ו-$4$ עם הערכים $-1$, $7$ ו-$-3$. בוב יכול להבטיח ניקוד של $7$ על ידי לקיחת אינדקס $3$ פעם אחת (הוספת הערך $7$). לאחר מכן, כל אינדקס שייבחר בהמשך חייב להיות לכל היותר $3$, ולכן לא ניתן לבחור באינדקס $4$, וכל מהלך חוקי נוסף מוסיף ערך אי-חיובי. אליס יכולה לכפות על בוב שלא יוכל להשיג יותר מ-$7$, ולכן התשובה היא $7$.
• מקרה בדיקה 2: מכיוון ש-$K = 0$, לאליס אין ברירה אלא $B = 0000$. כל האינדקסים זמינים לבוב, אך כל ערך במערך הוא שלילי. כל מהלך יקטין את הניקוד של בוב, ולכן המשחק האופטימלי של בוב הוא לא לבצע אף מהלך. לכן, התשובה היא $0$.
• מקרה בדיקה 3: מכיוון ש-$K = N$, לאליס אין ברירה אלא $B = 1111$. כל מיקום מוגן, ולכן לבוב אין אף מהלך חוקי. מכאן שהניקוד של בוב הוא $0$.