[SDOI2018] 荣誉称号

- Input file: title.in - Output file: title.out - Time limit: 10 seconds - Memory limit: 512 megabytes

休闲游戏玩家小 $Q$ 不仅在算法竞赛方面取得了优异的成绩，还在一款收集钻石的游戏中排名很高。 这款游戏一共有 $n$ 种不同类别的钻石，编号依次为 $1$ 到 $n$。小 $Q$ 已经玩了这款游戏很久了，对于第 $i$ 种钻石，他已经收集到了 $a_i$ 个。这款游戏最大的亮点就是，钻石只有一种获得途径，那就是从商城中购买。具体来说，第 $i$ 种钻石的单价为 $b_i$ 点券。为了鼓励玩家充值，每种钻石都没有数量上限，只要肯充钱，就可以拥有任意多的钻石。但是这款游戏并没有开发 “丢弃道具” 功能，因此小 $Q$ 不能通过丢弃钻石去完成任务。 最近这款游戏推出了一个限时成就任务，完成任务的玩家可以获得荣誉称号，而完成任务条件则是： 给定正整数 $k$ 和 $m$，对于任意一个整数 $x (x\ge 2^k)$，$a_{x}+a_{\lfloor\frac{x}{2}\rfloor}+a_{\lfloor\frac{x}{4}\rfloor}+a_{\lfloor\frac{x}{8}\rfloor}+...+a_{\lfloor\frac{x}{2^k}\rfloor}$ 都要是 $m$的倍数。 高玩小 $Q$ 当然想完成这个限时成就任务，但是在充钱之前他想知道他究竟需要多少点券才能完成这个任务。请写一个程序帮助小 $Q$ 计算最少需要的点券数量。

第一行包含一个正整数 $T$，表示测试数据的组数。 每组数据第一行包含 $9$ 个正整数 $n, k, m, p, SA, SB, SC, A, B$，其中 $n$ 表示钻石种类数，$k, m$ 表示任 务条件。 为了在某种程度上减少输入量，$a[]$ 和 $b[]$ 由以下代码生成： ``` unsigned int SA, SB, SC;int p, A, B; unsigned int rng61(){ SA ^= SA << 16; SA ^= SA >> 5; SA ^= SA << 1; unsigned int t = SA; SA = SB; SB = SC; SC ^= t ^ SA; return SC; } void gen(){ scanf("%d%d%d%d%u%u%u%d%d", &n, &k, &m, &p, &SA, &SB, &SC, &A, &B); for(int i = 1; i <= p; i++)scanf("%d%d", &a[i], &b[i]); for(int i = p + 1; i <= n; i++){ a[i] = rng61() % A + 1; b[i] = rng61() % B + 1; } } ```

对于每组数据，输出一行一个整数，即最少需要的点券数量。

2
3 1 2 3 11111 22222 33333 1 1
1 5
2 3
3 6
7 2 3 7 11111 22222 33333 1 1
6 9
4 5
3 7
5 2
2 4
1 7
9 6

3
14

- $1 ≤ T ≤ 10$， - $1 ≤ k ≤ 10$ 且 $2^k ≤ n$， - $ 1 ≤ p ≤ min(n, 100000)$，$10000 ≤ SA, SB, SC ≤ 1000000$， - $ 1 ≤ A, B, ai, bi ≤ 10^7$。 子任务 $1$（$30$ 分）：满足 $1 ≤ n ≤ 1000$ 且 $m = 2$。 子任务 $2$（$40$ 分）：满足 $1 ≤ n ≤ 10^5$ 且 $m ≤ 200$。 子任务 $3$（$30$ 分）：满足 $1 ≤ n ≤ 10^7$ 且 $m ≤ 200$。