Source : 2016年NOIP提高组
Description
Input

第一行包含一个正整数T,表示游戏的关卡总数。

下面依次输入这T个关卡的信息。每个关卡第一行包含两个非负整数n,m,分别表示该关卡中的小猪数量和Kiana输入的神秘指令类型。接下来的n行中,第i行包含两个正实数(xi,yi),表示第i只小猪坐标为(xi,yi)。数据保证同一个关卡中不存在两只坐标完全相同的小猪。

如果m=0,表示Kiana输入了一个没有任何作用的指令。
如果m=1,则这个关卡将会满足:至多用n/3+1只小鸟即可消灭所有小猪。
如果m=2,则这个关卡将会满足:一定存在一种最优解,其中有一只小鸟消灭了至少n/3只小猪。

保证1<=n<=18,0<=m<=2,0<xi,yi<10,输入中的实数均保留到小数点后两位。

Output

对每个关卡依次输出一行答案。

输出的每一行包含一个正整数,表示相应的关卡中,消灭所有小猪最少需要的小鸟数量

Sample Input
2
2 0
1.00 3.00
3.00 3.00
5 2
1.00 5.00
2.00 8.00
3.00 9.00
4.00 8.00
5.00 5.00
Sample Output
1 1
Hint
【样例说明】
这组数据中一共有两个关卡。
第一个关卡与【问题描述】中的情形相同,2只小猪分别位于(1.00,3.00)和(3.00,3.00),只需发射一只飞行轨迹为y = −x2 + 4x的小鸟即可消灭它们。
第二个关卡中有 5 只小猪,但经过观察我们可以发现它们的坐标都在抛物线y = −x2 + 6x上,故 Kiana 只需要发射一只小鸟即可消灭所有小猪。