| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 (추가 시간 없음) | 2048 MB | 32 | 20 | 19 | 65.517% |
You have $n$ videos on your watchlist on the popular platform YooCube. The $i$-th video lasts $d_i$ minutes.
YooCube has recently increased the frequency of their ads. Ads are shown only between videos. After finishing a video, an ad is shown if either of these two conditions is true:
You want to watch the $n$ videos in your watchlist. Given that you have just watched an ad, and that you can choose the order of the $n$ videos, what is the minimum number of ads that you are forced to watch? You can start a new video immediately after the previous video or ad ends, and you don’t have to watch any ad after you finish.
Each test contains multiple test cases. The first line contains an integer $t$ (1ドル ≤ t ≤ 100,円 000$) — the number of test cases. The descriptions of the $t$ test cases follow.
The first line of each test case contains two integers $n$ and $k$ (1ドル ≤ n ≤ 100,円 000,ドル 1ドル ≤ k ≤ 30,円 000$) — the number of videos in your watchlist and the parameter that determines when ads are shown.
The second line contains $n$ integers $d_1, d_2, \dots , d_n$ (1ドル ≤ d_i ≤ 10,円 000$) — the lengths of the videos.
The sum of the values of $n$ over all test cases does not exceed 10ドル^6$.
For each test case, print the minimum number of ads that you need to watch.
5 8 25 4 5 18 3 17 17 18 14 7 21 20 14 1 4 20 8 4 8 1 20 5 9 4 14 12 2 20 8 37 2 13 13 11 12 19 16 18 4 38 15 3 14 7
2 2 7 2 1
In the first test case, a possible viewing order is 4ドル,ドル 1ドル,ドル 8ドル,ドル 2ドル,ドル 5ドル,ドル 6ドル,ドル 7ドル,ドル 3ドル$ (the corresponding lengths being 3ドル,ドル 4ドル,ドル 14ドル,ドル 5ドル,ドル 17ドル,ドル 17ドル,ドル 18ドル,ドル 18ドル$). With this order, you will have to watch an ad after the first three videos and then another after the second three videos. Note that you don’t have to watch an ad after you finish watching all your videos.