雾粉与优先队列
时间限制：C/C++/Rust/Pascal 4秒，其他语言8秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

给两个长度为 n 的正整数数组 cnt, val，和三个正整数 x, y, k，你要恰好选择 k 次可以相同的下标，每次选择一个下标 1 \le i \le n 满足 cnt[i] > 0，你选择的总费用会增加 val[i]，且 cnt[i] 减一，同时 val[i] 变成 val[i] + x + (\gcd(val[i], y))，求最小总费用模 10^9+7 (取模是求出最小答案后取模，不是取模后最小答案)。

输入描述:

第一行包含四个正整数 n, x, y, k。
第二行包含 n 个正整数，第 i 个正整数表示 cnt[i]。
第三行包含 n 个正整数，第 i 个正整数表示 val[i]。

题目保证对于所有测试用例：
1 \le n, x, y \le 10^5
1 \le k \le \sum{cnt}
1 \le k, cnt[i], val[i] \le 10^9

输出描述:

输出一个非负整数，表示最小答案模 10^9+7 后的值
示例1

输入

复制 
3 1 3 4
1 2 3
1 3 2

输出

复制 
10

说明

第一次选择 i = 1，总费用加 1，cnt 变为 [0, 2, 3]， val变为 [1 + 1 + \gcd(1, 3), 3, 2] = [3, 3, 2]
第二次选择 i = 2，总费用加 3，cnt 变为 [0, 1, 3]， val变为 [3, 3 + 1 + \gcd(3, 3), 2] = [3, 7, 2]
第三次选择 i = 3，总费用加 2，cnt 变为 [0, 1, 2]， val变为 [3, 7, 2 + 1 + \gcd(2, 3)] = [3, 7, 4]
第四次选择 i = 3，总费用加 4，cnt 变为 [0, 1, 1]， val变为 [3, 7, 4 + 1 + \gcd(4, 3)] = [3, 7, 6]
示例2

输入

复制 
1 1 3 4
4
1000000000

输出

复制 
999999995

说明

不开 long long 见祖宗