9557: 持家

身为魔法少女的小 hua 可能从未考虑过，是否也会有要肩负起家庭与责任的一天。

小 hua 在拼夕夕上想购买原价为 $P$ 元的商品，由于拼夕夕是良心商家，他提前发放了 $n$ 张优惠券给小 hua。

本次购物，小 hua 被允许按照任意顺序使用 $k$ 张优惠券。

优惠券分两种：

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

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

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

对于每组数据：

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

接下来 $n$ 行，每行两个整数 ti，piti，pi。

ti=0ti=0 表示这张券可以打 pipi 折(1≤pi≤91≤pi≤9)。

ti=1ti=1 表示这张券可以减 pipi 元(1≤pi≤1091≤pi≤109)。