let $$$k$$$ = min(k,maximum no. of nodes that can be taken)
$$$k*h$$$ is small

Also, nice try on the Alien's trick solutions. Most of the solutions were that. Simple edge case for that:
$$$n = 4$$$
$$$A[1] = 9,A[2] = 5,A[3] = 5,A[4] = 5$$$
edges: $$$1-2,1-3,1-4$$$
Answer for $$$h = 2$$$ and $$$k = 1,2,3$$$ respectively is $$$9,10,15$$$
The function isn't convex.
(Actually, the initial intended solution was Alien's trick but we quickly found that it didn't work)

Sad to see no ACs on this problem :'(

First find the connected components for the graph. consider the edges in spanning tree(MST) of every connected connected component ,they will be considered in the final edges list answer since every spanning tree in each connected component will be bipartite.

Now we just need to connect these connected components using (no of CCs-1) new edges.

We will create a sorted vector of $$$pair<int,pair<int,int»$$$ which will store
{index of connected components,{value A[i],node}}
Let c=no of connected components so we find the position of transition from first index to next index and will add $$$abs(A[i]-A[i-1])$$$ in final weight and add edges $$${i,i-1}$$$ in final edge list.

like for first test case
sorted vector is {0,{1,1}},{1,{2,2}},{1,{3,3}},{1,{4,4}},{1,{5,5}} we will find which new edge to add using upper_bound({c,{1e9+5,1e9+5}}) for every c and calculate the final answer weight and list of edges.

1 ABES Engineering College
2 ABV-Indian Institute of Information Technology & Management Gwalior
3 Academy of Technology, Hooghly
4 Acropolis Institute of Technology & Research
5 Adani Institute of Infrastructure Engineering
6 Ajay Kumar Garg Engineering College, Ghaziabad
7 Aligarh Muslim University
8 Amity University Uttar Pradesh Lucknow Campus
9 Amrita School of Engineering, Coimbatore
10 Amrita School of Engineering, Kollam
11 Anil Neerukonda Institute of Technology and Sciences
12 Army Institute of Technology
13 Assam Engineering College
14 Atharva College of Engineering
15 B.N.M. Institute Of Technology
16 BIT Sindri
17 BITS PILANI, PILANI CAMPUs
18 BITS-Pilani, Goa Campus
19 BITS-Pilani, Hyderabad Campus
20 BML Munjal University
21 Bengal Institute of Technology, Tech Town
22 Bennett University
23 Bharati Vidyapeeth's College of Engineering, Delhi
24 Bhilai Institute of Technology, Durg
25 Birla Institute of Technology & Science, Pilani Campus
26 Birla Institute of Technology, Jaipur
27 Birla Institute of Technology, Mesra
28 Birla Institute of Technology, Patna
29 Birla Vishvakarma Mahavidyalaya Engineering College
30 Bundelkhand Institute of Engineering & Technology, Jhansi
31 C.V. Raman College Of Engineering
32 CMR College of Engineering & Technology
33 CMR Institute of Technology, Bangalore
34 CMR Technical Campus
35 CMR University
36 CV Raman College of Engineering, Bhubaneswar
37 CVR College of Engineering
38 Chaitanya Bharathi Institute of Technology
39 Chandigarh College of Engineering and Technology, Chandigarh
40 Chandigarh University
41 Chennai Mathematical Institute
42 Chitkara Institute of Engineering and Technology
43 Chitkara University
44 Christ University
45 College of Engineering and Technology
46 College of Engineering, Pune
47 D Y Patil International University
48 DAV Institute of Engineering And Technology
49 DIT University
50 DJ Sanghvi College of Engineering
51 DR. AKHILESH DAS GUPTA INSTITUTE OF TECHNOLOGY & MANAGEMENT
52 Dayananda Sagar College of Engineering
53 Dayananda Sagar University
54 Delhi Technological University
55 Delhi Technological University(Formerly DCE)
56 Department of Computer Science, University of Delhi
57 Devi Ahilya University
58 Dharmsinh Desai Institute of Technology
59 Dharmsinh Desai University
60 Dhirubhai Ambani Institute of Information and Communication Technology, Gandhinagar
61 Dr B R Ambedkar National Institute of Technology
62 Dr. APJ Abdul Kalam Technical University
63 Dr. Ambedkar Institute of Technology for Handicapped, Kanpur
64 Dr. B R Ambedkar National Institute of Technology, Jalandhar
65 Dr. Babasaheb Ambedkar Technological University
66 Dronacharya College of Engineering
67 Engineering College Bikaner
68 Fr. Conceicao Rodrigues College of Engineering, Mumbai
69 Future Institute of Engineering and Management, Kolkata
70 G H Patel College of Engineering & Technology
71 G.B. Pant Engineering College — Pauri India
72 G.H.Patel College of Engineering and Technology
73 GITAM (Deemed to be University)
74 GLA University, Mathura
75 Ganeshi Lal Bajaj Institute Of Technology And Management
76 Gaya College Of Engineering
77 Gokaraju Rangaraju Institute of Engineering and Technology, Hyderabad
78 Government College of Engineering and Ceramic Technology
79 Government College of Engineering, Amravati
80 Government College of Engineering, Aurangabad, Maharashtra
81 Government College of Engineering, Nagpur
82 Government College of Technology, Coimbatore
83 Government Engineering College Raipur
84 Government Engineering College, Bhavnagar
85 Govind B. Pant Univ. of Agril. & Tech
86 Govind Ballabh Pant Engineering College, Delhi
87 Graphic Era University
88 Guru Ghasidas University
89 Guru Jambheshwar University
90 Guru Nanak Institute of Technology
91 Gurukul Kangri Vishwavidyalaya
92 HMR Institute of Technology and Management
93 Haldia Institute of Technology, Kolkata
94 Harcourt Butler Technical University, Kanpur
95 Harcourt Butler Technological Institute — Kanpur
96 Heritage Institute of Technology, Kolkata
97 IIIT Vadodara
98 IIIT-Delhi
99 IIT Bhubaneswar
100 IMS Engineering College
101 INDIAN INSTITUTE OF INFORMATION TECHNOLOGY BHAGALPUR
102 INDIAN INSTITUTE OF INFORMATION TECHNOLOGY RANCHI
103 INDIAN INSTITUTE OF TECHNOLOGY GUWAHATI
104 Indian Institute Of Information Technology Agartala
105 Indian Institute Of Information Technology, Kottayam
106 Indian Institute Of Technology Jodhpur
107 Indian Institute of Engineering Science and Technology, Shibpur
108 Indian Institute of Information Technology & Management, Gwalior
109 Indian Institute of Information Technology — Allahabad
110 Indian Institute of Information Technology Allahabad
111 Indian Institute of Information Technology Bhopal
112 Indian Institute of Information Technology Design and Manufacturing Kancheepuram
113 Indian Institute of Information Technology Design and Manufacturing, Kurnool
114 Indian Institute of Information Technology Guwahati
115 Indian Institute of Information Technology Kalyani
116 Indian Institute of Information Technology Kota
117 Indian Institute of Information Technology Kottayam
118 Indian Institute of Information Technology Nagpur
119 Indian Institute of Information Technology Pune
120 Indian Institute of Information Technology Senapati, Manipur
121 Indian Institute of Information Technology Sri City
122 Indian Institute of Information Technology, Dharwad
123 Indian Institute of Information Technology, Kalyani
124 Indian Institute of Information Technology, Lucknow
125 Indian Institute of Information Technology, Sonepat
126 Indian Institute of Information Technology, Sri City, Chittoor
127 Indian Institute of Information Technology, Surat
128 Indian Institute of Information Technology, Una
129 Indian Institute of Information Technology,Una
130 Indian Institute of Technology (Banaras Hindu University), Varanasi
131 Indian Institute of Technology (ISM), Dhanbad
132 Indian Institute of Technology — Bhilai
133 Indian Institute of Technology — Bombay
134 Indian Institute of Technology — Delhi
135 Indian Institute of Technology — Gandhinagar
136 Indian Institute of Technology — Guwahati
137 Indian Institute of Technology — Hyderabad
138 Indian Institute of Technology — Indore
139 Indian Institute of Technology — Jodhpur
140 Indian Institute of Technology — Kanpur
141 Indian Institute of Technology — Kharagpur
142 Indian Institute of Technology — Madras
143 Indian Institute of Technology — Mandi
144 Indian Institute of Technology — Patna
145 Indian Institute of Technology — Roorkee
146 Indian Institute of Technology — Ropar
147 Indian Institute of Technology — Varanasi
148 Indian Institute of Technology Bhilai
149 Indian Institute of Technology Dharwad
150 Indian Institute of Technology Goa
151 Indian Institute of Technology Jammu
152 Indian Institute of Technology Kanpur
153 Indian Institute of Technology Kharagpur
154 Indian Institute of Technology Tirupati
155 Indian Institute of Technology and Management in Atal Bihari V
156 Indian Institute of Technology, Kanpur
157 Indian Institute of Technology, Palakkad
158 Indian Institute of Technology, Tirupati
159 Indian Institute of Technology-Tirupati
160 Indian Statistical Institute
161 Indira Gandhi Delhi Technical University for Women
162 Indore Institute of Science and Technology
163 Indraprastha Institute of Information Technology
164 Institute of Engineering & Technology — Devi Ahilya Univ.
165 Institute of Engineering & Technology, Lucknow
166 Institute of Engineering and Management, Calcutta
167 Institute of Engineering and Technology -DAVV -Indore
168 Institute of Technical Education & Research
169 International Institute of Information Technology — Bangalore
170 International Institute of Information Technology — Hyderabad
171 International Institute of Information Technology — Naya Raipur
172 International Institute of Information Technology Bhubaneswar
173 International Institute of Information Technology, Bangalore
174 JNTUH College of Engineering Hyderabad
175 JSS Academy Of Technical Education
176 JSS Academy of Technical Education Noida
177 Jabalpur Engineering College
178 Jadavpur University
179 Jadavpur University, Kolkata
180 Jaipur Engineering College & Research Centre
181 Jalpaiguri Government Engineering College- Maulana Abul Kalam Azad University of Technology
182 Jamia Milia Islamia
183 Jamia Millia Islamia
184 Jaypee Institute of Information Technology
185 Jaypee Institute of Information Technology University
186 Jaypee University of Engineering and Technology, Guna
187 Jaypee University of Information Technology
188 K. J. Somaiya College of Engineering, Vidyavihar, Mumbai
189 K.R. Mangalam University
190 KIET GROUP OF INSTITUTIONS
191 KIIT University
192 KLE Technological University
193 Kalinga Institute Of Industrial Technology,Bhubaneswar
194 Kalinga Institute of Industrial Technology
195 Kalyani Government Engineering College
196 Kamla Nehru Institute of Technology
197 Keshav Memorial Institute of Technology
198 L. D. College of Engineering
199 L.D. College of Engineering
200 LDRP Institute of Technology and Research
201 Lakshmi Narain College of Technology
202 Lovely Professional University
203 M. S. Ramaiah Institute of Technology
204 MBM College of Engineering, Jodhpur
205 MGM's Jawaharlal Nehru Engineering College
206 MIT ADT School of Engineering
207 MLR Institute of Technology
208 Madan Mohan Malaviya University of Technology-Gorakhpur
209 Madhav Institute of Technology & Science, Gwalior
210 Maharaja Agrasen Institute of Technology
211 Maharaja Surajmal Institute of Technology
212 Maharshi Dayanand University, Rohtak
213 Malla Reddy Engineering College
214 Malviya National Institute of Technology Jaipur
215 Manipal Institute of Technology
216 Manipal Institute of Technology, Manipal
217 Manipal University Jaipur
218 Maulana Abul Kalam Azad University of Technology, West Bengal
219 Maulana Azad National Institute of Technology Bhopal
220 Moradabad Institute of Technology
221 Motilal Nehru National Institute of Technology — Allahabad
222 Mukesh Patel School of Technology Management and Engineering, NMIMS University
223 NATIONAL INSTITUTE OF TECHNOLOGY TIRUCHIRAPPALLI
224 NIIT UNIVERSITY
225 NIT Andhra Pradesh
226 NIT KURUKSHETRA
227 NSS College of Engineering, Palakkad
228 Nalanda College Of Engineering, Chandi, Nalanda, Bihar
229 Narula Institute of Technology
230 National Institute of Engineering, Mysore
231 National Institute of Technology Agartala
232 National Institute of Technology Andhra Pradesh
233 National Institute of Technology Calicut
234 National Institute of Technology Delhi
235 National Institute of Technology Goa
236 National Institute of Technology Hamirpur
237 National Institute of Technology Karnataka, Surathkul
238 National Institute of Technology Manipur
239 National Institute of Technology Meghalaya
240 National Institute of Technology Patna
241 National Institute of Technology Puducherry, Karaikal
242 National Institute of Technology Uttarakhand
243 National Institute of Technology, Calicut
244 National Institute of Technology, Durgapur
245 National Institute of Technology, Hamirpur
246 National Institute of Technology, Jamshedpur
247 National Institute of Technology, Kurukshetra
248 National Institute of Technology, Meghalaya
249 National Institute of Technology, Patna
250 National Institute of Technology, Raipur
251 National Institute of Technology, Rourkela
252 National Institute of Technology, Silchar
253 National Institute of Technology, Srinagar
254 National Institute of Technology, Trichy
255 National Institute of Technology, Warangal
256 National institute of Technology, Uttarakhand
257 Netaji Subhash Engineering College, Kolkata
258 Netaji Subhash University Of Technology
259 Netaji Sushas University of Technology
260 Nirma Institute of Technology, Ahmedabad
261 Nirma University
262 Oriental Institute of Science and Technology — Bhopal
263 PDPM Indian Institute of Information Technology Design & Manufacturing, Jabalpur
264 PEC University of Technology
265 PES University Electronic City Campus
266 PSG College of Technology
267 PSG Institute of Technology and Applied Research
268 PVG's College of Engineering and Technology & G.K. Pate (Wani) Institute of Management
269 Padmasri Dr. B.V. Raju Institute Of Technology
270 Pandit Deendayal Petroleum University
271 Panjab University Swami Sarvanand Giri Regional Center
272 Pimpri-Chinchwad College Of Engineering
273 Pondicherry Engineering College
274 Pranveer SIngh Institute of Technology
275 Pune Institute of Computer Technology
276 Punjab Engineering College
277 Punjab Engineering College Chandigarh
278 RCC Institute of Information Technology, Beliaghata, Kolkata, West Bengal
279 RK University
280 RNS Institute of Technology
281 Raj Kumar Goel Institute of Technology
282 Rajasthan Institute of Engineering Technology, Jaipur
283 Rajasthan Technical University Kota
284 Rajiv Gandhi College of Engineering and Research, Nagpur
285 Rajiv Gandhi Institute Of Petroleum Technology
286 Rajiv Gandhi Institute of Technology, Mumbai
287 Ramkrishna Mahato Government Engineering College
288 Ramrao Adik Institute of Technology
289 Rashtreeya Vidyalaya College of Engineering
290 Rashtriya Raksha University
291 SIES Graduate School of Technology
292 SRM Institute Of Science and Technology
293 SRM Institute of Science and Technology, Ramapuram Campus
294 SRM University AP
295 SRM University NCR CAMPUS
296 Sant Longowal Institute of Engineering and Technology
297 Sardar Patel Institute of Technology
298 Sardar Vallabhbhai National Institute of Technology
299 Sastra University
300 Satish Chander Dhawan Government College Dist Ludhiana, Punjab
301 School of Engineering Cochin University of Science and Technology, Kochi
302 School of Engineering and Applied Science, Ahmedabad University
303 Shiv Nadar University
304 Shree L.R Tiwari College Of Engineering
305 Shri Govindram Seksaria Institute of Technology and Science
306 Shri Govindram Seksaria Institute of Technology and Science, Indore
307 Shri Guru Gobind Singhji Institue of Engineering and Technology
308 Shri Ramdeobaba College of Engineering and Management, Nagpur
309 Shri Shankaracharya Institute of Professional Management and Technology
310 Shri Vaishnav Vidyapeeth Vishwavidyalya
311 Sinhgad College of Engineering
312 Sir M. Visvesvaraya Institute of Technology
313 Sona College of Technology, Salem
314 Sri Sivasubramaniya Nadar College of Engineering
315 Sri Venkateswara College of Engineering
316 Sri Venkateswara College of Engineering, Tirupati
317 St. Joseph Engineering College, Mangalore
318 Swami Keshvanand Institute of Technology
319 Symbiosis Institute of Technology
320 TECHNO INDIA UNIVERSITY, WEST BENGAL
321 Techno Main Salt Lake (formerly known as Techno India Salt Lake)
322 Thadomal Shahani Engineering College
323 Thakur College of Engineering and Technology
324 Thapar Institute of Engineering & Technology
325 The LNM Institute of Information Technology
326 Thiagarajar College of Engineering
327 University College of Engineering and Technology, Vinoba Bhave University
328 University Institute of Engineering & Technology, CSJMU, Kanpur
329 University Institute of Engineering and Technology
330 University Institute of Engineering and Technology, Kurukshetra University
331 University Institute of Engineering and Technology, Panjab University
332 University Institute of Technology — RGPV
333 University School of Information Technology
334 University Visvesvaraya College of Engineering
335 University of Calcutta
336 VIT Bhopal University
337 VIT University Chennai Campus
338 VNR Vignana Jyothi Institute of Engineering & Technology
339 Vasavi College of Engineering
340 Vasireddy Venkatadri Institute of Technology
341 Veermata Jijabai Technological Institute
342 Velammal Engineering College
343 Vellore Institute of Technology
344 Vellore Institute of Technology — Andhra Pradesh
345 Vidyavardhini's College of Engineering and Technology
346 Vignan Institute of Technology & Science
347 Vishnu Institute of Technology
348 Vishwakarma Government Engineering College
349 Vishwakarma Institute of Information Technology
350 Vishwakarma Institute of Technology
351 Visvesvaraya National Institute of Technology, Nagpur
352 Vivekanand Education Society's Institute of Technology
353 Walchand College of Engineering, Sangli
354 YMCA University of Science and Technology, Faridabad
355 Yeshwantrao Chavan College of Engineering
356 Zakir Hussain College of Engineering & Technology — Amu

#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define double long double
#define F_IO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define consoleLog(str,x) clog<<"Debugging: "<<str<<" -> "<<x<<endl;
#define assertLog(state,lin) if(!state) clog<<"Error: "<<lin<<endl;

const int MAXN = 1e5 + 10;
const int MAX_ALPHA = 35;
string words[MAXN];
int n,q;
int dpWord[MAXN][MAX_ALPHA];
int cnt[MAX_ALPHA][MAX_ALPHA];
int mainDp[35][MAX_ALPHA][MAX_ALPHA];

// Making cnt[i][j] = 0.
void makeCntZero() {
    for (int i = 0; i < MAX_ALPHA; i++) {
        for (int j = 0; j < MAX_ALPHA; j++) {
            cnt[i][j] = 0;
        }
    }
}

// Filling dpWord for each string.
void fillDpLength(int idx) {

    for (int start = 0; start < 26; start++) {
        string wordTemp;

        // Only using those chararcters which are >= start.
        for (char c: words[idx]) {
            if (c - 'a' >= start) wordTemp.push_back(c);
        }

        // making dpWord = 0 for computing.
        for (int i = 0; i < wordTemp.size(); i++) {
            for (int last = 0; last < MAX_ALPHA; last++) {
                dpWord[i][last] = 0;
            }
        }

        // Calculation LIS from a string starting with start
        // and ending with whatever possible last character is.
        for (int i = 0; i < wordTemp.size(); i++) {
            int word = wordTemp[i] - 'a';

            if (i == 0) {
                dpWord[i][word] = 1;
            } else {
                for (int last = 0; last < MAX_ALPHA; last++) {
                    dpWord[i][last] = dpWord[i-1][last];
                }

                for (int last = 0; last <= word; last++) {
                    dpWord[i][word] = max(dpWord[i][word], dpWord[i-1][last] + 1);
                }
            }
            
            // Saving result for a particular start and end character.
            cnt[start][word] = max(cnt[start][word], dpWord[i][word]);
        }
    }
}

void fillMainDp() {


    // For safety purpose need to remove
    for (int i = 0; i < MAX_ALPHA; i++) {
        for (int j = i; j < MAX_ALPHA; j++) {
            for (int k = i; k <= j; k++) {
                cnt[i][j] = max({cnt[i][k],cnt[k][j],cnt[i][j]});
            }
        }
    }
   
    // Making mainDp = 0 for computation.
    for (int i = 0; i <= 32; i++) {
        for (int word = 1; word < MAX_ALPHA; word++) {
            for (int word2 = 0; word2 < MAX_ALPHA; word2++) {
                mainDp[i][word][word2] = 0;
            }
        }
    }

    // Calculating mainDp i.e. maximum possible length with newWord as 
    // the last word.
    for (int i = 1; i <= 32; i++) {
        for (int prevWord = 0; prevWord < MAX_ALPHA; prevWord++) {
            for (int newWord = prevWord; newWord < MAX_ALPHA; newWord++) {
                
                mainDp[i][prevWord][newWord] = mainDp[i-1][prevWord][newWord];
                for (int word = prevWord; word <= newWord; word++)
                    mainDp[i][prevWord][newWord] = max(mainDp[i][prevWord][newWord], mainDp[i-1][prevWord][word] + cnt[word][newWord]);
            }
        }
    }

}

signed main() {
    F_IO;

    int t; cin>>t;

    while(t--) {

        cin>>n>>q;
        makeCntZero();

        for (int i = 1; i <= n; i++) {
            cin>>words[i];
        }        

        for (int i = 1; i <= n; i++) {
            fillDpLength(i);
        }

        fillMainDp();
        int ans = 0;

        if (q <= 30) ans = mainDp[q][0][MAX_ALPHA-1];
        else ans = mainDp[30][0][MAX_ALPHA-1] + (q - 30) * (mainDp[32][0][MAX_ALPHA-1] - mainDp[31][0][MAX_ALPHA-1]);

        cout<<ans<<endl;
    }
}