You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

飞飞鸳鸯鸟，举翼相蔽亏。

俱来绿潭里，共向白云涯。

音容相眷恋，羽翮两逶迤。

蘋萍戏春渚，霜霰绕寒池。

浦沙连岸净，汀树拂潭垂。

年年此游玩，岁岁来追随。

—— 唐·陈子昂《鸳鸯篇》

题目描述

下课了，BC 学校的同学们来到操场上做活动。

有 $N$ 个活动，每个活动有两个参数 $h_i$ 和 $t_i$，其中 $h_i$ 指如果参加活动 $i$ 则会获得 $h_i$ 的快乐值，$t_i$ 表示如果参加活动 $i$ 则会耗费 $t_i$ 的体力值。

已知同学们想获得 $\ge H$ 的快乐值，且他们做的活动的编号必须连在一起。现在请你为同学们在 $N$ 个活动中选择一些活动，使得在满足条件的情况下耗费的总体力值最小。求这个最小值。

输入格式

注意：由于本题读入量巨大，所以无需读入 $h$ 和 $t$ 数组。具体构造方式见下。

本题共有 $T$ 组测试数据，共输入 $T + 1$ 行。

• 第 $1$ 行：$1$ 个整数 $T$，表示测试数据数量。
• 第 $2 \sim T + 1$ 行，第 $q + 1$ 行表示第 $q$ 组测试数据。

对于每组测试数据：

• $1$ 行 $8$ 个整数 $N, H, A, B, C, D, E, F$，表示一共有 $N$ 个活动，同学们希望快乐值最少为 $H$，$A, B, C$ 用于构造 $h$ 数组，$D, E, F$ 用于构造 $t$ 数组。具体构造方式如下：
  • $h_i = \left\{\begin{matrix}A & (i = 1)\\(h_{i - 1} \times B + C) \mod 1000000000 + 1 & (2 \le i \le N)\end{matrix}\right.$
  • $t_i = \left\{\begin{matrix}D & (i = 1)\\(t_{i - 1} \times E + F) \mod 1000000000 + 1 & (2 \le i \le N)\end{matrix}\right.$

输出格式

共输出 $T$ 行：

• 第 $q$ 行：$1$ 个整数表示测试数据 $q$ 的最小的体力值。

样例

1
5 760 4 5 3 10 4 6

1029

共有 $5$ 个活动，同学们希望快乐值最小为 $760$，每个活动的快乐值分别为 $4, 24, 124, 624, 3124$，体力值分别为 $10, 47, 195, 787, 3155$。

选择做 $2, 3, 4$ 这些活动，获得快乐值为 $24 + 124 + 624 = 772 \ge 760$，耗费体力值为 $47 + 195 + 787 = 1029$。可以证明。这是最小的体力值。

数据范围

• 对于 $100\%$ 的数据，$3 \le T \le 15$，$1 \le N\le 5 \times 10^6$，$1 \le h_i, t_i \le 10^8$，$H \le \sum h_i$。
• 提示：你可以通过 $T$ 的个位数判断此测试点属于哪个 $\text{Subtask}$。

模板

您可以直接 Copy 下面的代码，其中读入部分已经完善，只需要在 Solve() 函数处完成自己的代码即可。

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int MAXN = 5000010;

int T, N, H, A, B, C, D, E, F, h[MAXN], t[MAXN];

inline void Input()
{
	scanf("%lld%lld%lld%lld%lld%lld%lld%lld", &N, &H, &A, &B, &C, &D, &E, &F);
	
	h[1] = A;
	for (int i = 2; i <= N; ++ i )
		h[i] = (h[i - 1] * B + C) % 100000000 + 1;
	
	t[1] = D;
	for (int i = 2; i <= N; ++ i )
		t[i] = (t[i - 1] * E + F) % 100000000 + 1;
	
	return;
}

inline int Solve()
{
	// Write Code Here ~
	
}

signed main()
{
	scanf("%lld", &T);
	
	while (T -- )
	{
		Input();
		printf("%lld\n", Solve());
	}
	
	return 0;
}