Masala #RXMGMMOZPH

Berilgan: butun sonlardan tashkil topgan  $a$  massivi, uzunligi  $n$  bo‘lgan  $(a_1, a_2, ..., a_n)$  va bir butun son  $k$ .

Sizdan bo‘sh bo‘lmagan (ya’ni, kamida bitta elementdan iborat) qism massiv  $a_l, a_{l+1}, ..., a_r$  ni tanlab, quyidagi operatsiyalardan birini bajarishingiz talab qilinadi:

1. Tanlangan qism massivning barcha elementlarini  $k$  ga ko‘paytirish, ya’ni  $a_i := k \cdot a_i \quad (l \le i \le r)$ .
2. Tanlangan qism massivning barcha elementlarini   $k$ ga bo‘lish, natijani pastga yaxlitlash bilan, ya’ni $a_i := \left\lfloor \frac{a_i}{k} \right\rfloor \quad(l \le i \le r)$ .

$\lfloor x \rfloor$ $x$ ga teng yoki undan kichik bo‘lgan eng katta butun sonni ifodalaydi. Masalan, $\lfloor 3.5 \rfloor = 3$ va $\lfloor -3.5 \rfloor = -4$.

$a$  massividagi barcha qism massivlar orasida, bitta bo‘sh bo‘lmagan qism massivni tanlab, unga yuqoridagi operatsiyalardan birini qo‘llagandan keyin tanlangan massiv yig‘indisining maksimal qiymati qancha bo‘lishi mumkin operatsiyani qo'llashdan keyin faqat bir marta?
 

Birinchi qatorda bitta butun son berilgan:

$t (1 \le t \le 10^4)$ – test holatlarining soni.

Har bir test holatining birinchi qatori ikkita butun sondan iborat:

$n$, $k$ ($1 \le n \le 2 \cdot 10^5$, $-10^9 \le k \le 10^9$) – massiv uzunligi $a$ va butun son $k$.

Har bir test holatining ikkinchi qatori $n$ ta ajratilgan butun sonlarni o‘z ichiga oladi: $a_1, a_2, ..., a_n$ ($-10^4 \le a_1, a_2, ..., a_n \le 10^4$) – massiv $a$.

Shuningdek, $n$ ning yig‘indisi barcha testlarda $2 \cdot 10^5$ dan oshmasligi kafolatlangan.

Har bir test holati uchun bitta butun sonni chiqarish kerak: tanlangan $\bf{bo'sh \ emas}$ qism massivning maksimal yig'indisi.