There was a kingdom

Time Limit: 4000/2000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

Description

Once upon a time, there was a kingdom ruled by a wise king.
After years of his reign, by means of successful economic actions, the kingdom, with n cities, became an economic power soon.
Without nation defense, the development of the state economy will be hurt, the king said.
After days of serious thoughts, the king finally decided to choose k cities to cover as more area as possible (the area covered by k cities equals to the area of the convex formed by these k points).
However, the king don't know how to choose the optimal way to do it. Please help him!

Input

The input consists of multiple test cases.
The first line of the input gives the number of test cases, T ($1 \leq T \leq 200$). T test cases follow.
Each test case starts with two integer n ($1 \leq n \leq 100$) and k ($1 \leq k \leq n$).
Then following n lines contains two integers x and y, the coordinates of the cities.
$-10^7 \leq x \leq 10^7$, $-10^7 \leq y \leq 10^7$.
It is guaranteed that there are no more than 30 test cases in which $n \geq 50$.

Output

Please output "Case #k: res", k is the number of test case and res is maximum area multiply 2, to make sure res is always an integer.

Sample Input

1 5 3 10 -2 -7 -10 -3 -8 -10 10 -10 5

Sample Output

Case #1: 364

Hint

hujie

Source

2015 ACM/ICPC Asia Regional Shanghai Online

提交代码