D. Card Game

You're playing a card game with K friends of yours, and since you're a champion in this game, they will play together and you will only play with the winner. And now when they are playing your job is just to deal N cards and distribute them among your friends, you can choose how to distribute them, but the distribution should satisfy these rules: 1- Each player must have a continuous subsequence of the original set. 2- Each card must be dealt to some player. 3- Each player must have at least one card. Note that it is not important that players have the same number of cards. You know that all of them are playing using the same strategy so the player with the maximum card group power will win. Each card has a power P the power of group of cards is calculated as (the number of cards in that group) * (the maximum value in the same group). Since the winner will play with you, and he will play using the same group of cards, you decided to minimize the power of his cards as much as you can. Write a program to help you to do so. In the first line one integer T the number of test cases. For each test case there will be two integers N and K (1 ≤ N ≤ 1000000 , 1 ≤ K ≤ min(N, 20000)), then N integers representing the power of the cards in the original set and their order. (1 ≤ Pi ≤ 1000000). For each test case print a single line containing one integer which is the minimum group power you can make the winner player have. ## Input In the first line one integer T the number of test cases. For each test case there will be two integers N and K (1 ≤ N ≤ 1000000 , 1 ≤ K ≤ min(N, 20000)), then N integers representing the power of the cards in the original set and their order. (1 ≤ Pi ≤ 1000000). ## Output For each test case print a single line containing one integer which is the minimum group power you can make the winner player have. [samples]