Farmer John owns a lot of cows that graze in the fields and walk around happily. 现在John 有G个金币，他可以用这些金币够买化肥，也能用来购置饲料。John拥有n头牛崽和m块种有特定作物的农田。John将一头牛崽养大或让一块农田的作物成熟都要花费一定数量的金币来购买饲料或化肥，每当他收获一头牛或一块作物田，他就能收获一点happy值。想要收获不同的作物和cows所需花费的金币数也不同。由于John不喜欢吃肉，所以他就将牛肉和精灵交换，作为交换条件，精灵会使用魔法来帮助John立刻收获一定数量的牛或作物（当然可以一部分是牛崽，另一部分是作物。如：精灵可以帮助John收获4个数量的牛或作物，那么，John可以选择让1头牛和3个作物收获，或2个牛和2个作物能收获，也可以让4个牛能收获，更或者让4个作物能收获。此外数据保证John至少能收获一个）。现在John想要知道自己最多能获得多少点happy值，同时花费的金币数量最少。

输入数据的第一行是一个数据T，表示有T组数据。每组测试数据的第一行是三个数G, n, m（1<=G<=10,000 0<=n<=100 0<=m<=100 1<=n + m<=200) 分别表示John所拥有的金币数，牛崽的个数和种有作物的农田数，接下来n行，每一行有两个数ai, bi(1<=ai<=10,000 1<=bi<=1,000)分别表示第i头牛崽需要花费ai的金币才能养大，与精灵交换能获得bi数量的牛崽或作物能被收获。接下来m行，每一行有一个数ci，表示让第i个作物种熟需要花费ci个金币。

对于每组输入数据，先输出单独一行"Case #i:"（其中i表示第i组测试数据，从1开始）接下来输出一行。两个数分别表示剩余的happy值和金币数。

首先，John花费20金币收获两头牛，这样，John就获得了两点happy，然后将两头牛去和精灵交换，精灵可以让John能立刻收获4个单位的牛崽或作物，此时，John选择收获4个单位的作物，这样，4个作物就被收获了，John也随即获得了4点happy。所以，最终答案为剩余0个金币和2+4=6点happy。

The 12th ZJNU Anniversary Contest