Problem Description

身为魔法少女的小 hua 可能从未考虑过，是否也会有要肩负起家庭与责任的一天。 小 hua 在拼夕夕上想购买原价为 $P$ 元的商品，由于拼夕夕是良心商家，他提前发放了 $n$ 张优惠券给小 hua。 本次购物，小 hua 被允许 **按照任意顺序** 使用 $k$ 张优惠券。

优惠券分两种：

1. 打折券，打 $x$ 折，其中 $x\in \{1, 2, 3, \dots, 9\}$。
2. 减免券，直接减 $x$ 元。

商家不会倒贴钱给他，她的花费最少是 $0$ 元。优惠券均可叠加，例如使用两张 $8$ 折券，则可以以 $6.4$ 折的价格买下商品。

Input

第一行一个整数 $T$ 表示测试数据组数。

对于每组数据：

一行三个整数 $P, n, k$ 表示商品初始价格、优惠券张数、优惠券使用上限。

接下来 $n$ 行，每行两个整数 $t_i，p_i$。

$t_i=0$ 表示这张券可以打 $p_i$ 折($1 \leq p_i \leq 9$)。

$t_i=1$ 表示这张券可以减 $p_i$ 元($1 \leq p_i \leq 10^9$)。

Output

对于每组数据，输出一行一个浮点数（**保留两位小数**）表示买下商品的最小花费。

3
79 4 2
0 9
1 14
0 5
0 8
71 4 3
1 22
1 3
0 6
0 7
70 5 3
1 18
0 2
0 1
0 9
1 7

25.50
7.82
0.00

Hint

对于所有数据：$1 \leq T \leq 100, 1 \leq n \leq 10^4, 1 \leq P \leq 10^9, 1 \leq k \leq n$。