Minimum Maximum Confusion

Problem description.
You are given two sequences of N elements P and Q. You have to partition them where the cost of making a partition from index L to R is cost = min(P[L...N])*max(Q[1...R]). Find the minimum and the maximum cost of partitioning the two sequences into exactly K partitions. Remember, the partitions of the two sequences must be the same, you cannot make different partitions for P and Q.
Input
Input description.
The first line of the input contains an integer T denoting the number of test cases. T test cases follow. The first line of each test case contains a two integers N and K denoting the number of elements in the sequences and the number of partitions to be made. Then follows N lines, each line containing two integers, the first element corresponding the P and the second integer corresponding to Q.
Output
For each test case, output a single line containing two integers denoting minimum and maximum cost.
Constraints
 1 ≤ T ≤ 10
 1 ≤ K ≤ N ≤ 1000
 10^{5} ≤ P_{i}, Q_{i} ≤ 10^{5}
Subtasks
Subtask #1(9 points):
 1 ≤ N ≤ 1000
 K = 2
 1 ≤ K ≤ N ≤ 1000
 1 ≤ P_{i}, Q_{i} ≤ 10^{5}
 1 ≤ K ≤ N ≤ 100
 Original Constraints
Example
Input: 3 5 1 1 1 2 2 3 3 4 4 5 5 5 5 1 1 2 2 3 3 4 4 5 5 5 2 1 1 2 2 3 3 4 4 5 5 Output: 5 5 55 55 11 29
Explanation
Example case 1.
There is only one way to partition the elements and that is to keep everything in the same partition, i.e, [1, 5]. The cost is min(P[1..N])*max(Q[1..N]) = 1*5 = 5.
This is both the maximum and the minimum possible.
Author:  ista2000 
Tags  convexhulloptimization, dynamicprogramming, icop1806, ista2000, mediumhard 
Date Added:  2012018 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 