Comet OJ

C0701 [SDOI2018]荣誉称号

内存限制：512 MB 时间限制：10000 ms

题目描述

休闲游戏玩家小 Q 不仅在算法竞赛方面取得了优异的成绩，还在一款收集钻石的游戏中排名很高。

这款游戏一共有 $n$ 种不同类别的钻石，编号依次为 $1$ 到 $n$。小 Q 已经玩了这款游戏很久了，对于第 $i$ 种钻石，他已经收集到了 $a_i$ 个。这款游戏最大的亮点就是，钻石只有一种获得途径，那就是从商城中购买。具体来说，第 $i$ 种钻石的单价为 $b_i$ 点券。为了鼓励玩家充值，每种钻石都没有数量上限，只要肯充钱，就可以拥有任意多的钻石。但是这款游戏并没有开发"丢弃道具"功能，因此小 Q 不能通过丢弃钻石去完成任务。

最近这款游戏推出了一个限时成就任务，完成任务的玩家可以获得荣誉称号，而完成任务条件则是：给定正整数 $k$ 和 $m$，对于任意一个整数 $x(2^k\leq x\leq n)$，

$\large a_x+a_{\left\lfloor\frac{x}{2}\right\rfloor}+a_{\left\lfloor\frac{x}{4}\right\rfloor}+a_{\left\lfloor\frac{x}{8}\right\rfloor}+...+a_{\left\lfloor\frac{x}{2^k}\right\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;
    }
}

输出

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

样例

样例输入 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

样例输出 1

3
14

提示

$1\le T\le 10$，$1\le k\le 10$ 且 $2^k\le n$，$1\le p\le \min(n,10^5)$，$10^4\le SA,SB,SC\le 10^6$，$1\le A,B,a_i,b_i\le 10^7$。

子任务1（30分）：满足 $1\le n\le 1000$ 且 $m=2$。

子任务2（40分）：满足 $1\le n\le 10^5$ 且 $m\le 200$。

子任务3（30分）：满足 $1\le n\le 10^7$ 且 $m\le 200$。