Pandalla on yksiulotteinen akseli, jonka ei-negatiiviselle puolelle on asetettu $n$ janaa. $i$-nnen janan vasen päätepiste on $l_i$. Jokaisella janalla on sama pituus, $L$. Tämä tarkoittaa, että $i$-s jana peittää suljetun välin $[l_i, l_i + L - 1]$.
Nyt Panda haluaa sinun etsivän suurimman mahdollisen määrän akselin ei-negatiivisella puolella olevia kokonaislukupisteitä, jotka voidaan peittää täsmälleen $k$ kertaa, kun siirretään enintään yhtä janaa. Tarkemmin sanoen saat valita enintään yhden janan ja muuttaa sen vasemman päätepisteen miksi tahansa ei-negatiiviseksi kokonaisluvuksi (ilman ylärajaa). Janan pituus $L$ pysyy samana.
Syöte
Ensimmäinen rivi sisältää kokonaisluvun $T$ ($1 \le T \le 2 \times 10^5$), joka ilmoittaa testitapausten lukumäärän.
Jokaisessa testitapauksessa ensimmäinen rivi sisältää kolme positiivista kokonaislukua $n, L, k$ ($1 \le n \le 2 \times 10^5$, $1 \le L \le n$, $1 \le k \le n$). $n$ on janojen kokonaismäärä, $L$ on jokaisen janan kiinteä pituus ja $k$ on vaadittu peittokertojen määrä.
Toinen rivi sisältää $n$ ei-negatiivista kokonaislukua. $i$-s kokonaisluku on $l_i$ ($0 \le l_i \le 2 \times n$), joka esittää $i$-nnen janan vasenta päätepistettä.
On taattu, että lukujen $n$ summa yli kaikkien testitapausten ei ylitä arvoa $2 \times 10^5$.
Tuloste
Tulosta jokaiselle testitapaukselle yksi rivi, jolla on yksi kokonaisluku: suurin mahdollinen määrä kokonaislukupisteitä, jotka voidaan peittää täsmälleen $k$ kertaa, kun siirretään enintään yhtä janaa.
Esimerkit
Syöte 1
3 3 2 1 2 6 2 3 3 2 6 2 0 5 1 3 5 6 7 8 9
Tuloste 1
6 3 0
Huomautus
Esimerkin ensimmäisessä testitapauksessa kolme janaa ovat aluksi $[2, 3]$, $[6, 7]$ ja $[2, 3]$. Voit muuttaa kolmannen janan vasemmaksi päätepisteeksi $114514$. Tämän siirron jälkeen janat ovat $[2, 3]$, $[6, 7]$ ja $[114514, 114515]$. Tällöin $6$ kokonaislukupistettä peittyy täsmälleen kerran, mikä on suurin saavutettavissa oleva määrä.
Toisessa testitapauksessa voit siirtää ensimmäisen janan vasemman päätepisteen kohtaan $3$ maksimoidaksesi täsmälleen kahdesti peittyvien kokonaislukupisteiden määrän.