#1642. 有趣的题

有趣的题

题目描述

Fly 创造了一个属于他的函数,这个函数是这样的(其中 SS 是个集合):

$$\mathit{Fly}(S,t)= \begin{cases} \min\lbrace a_i+\mathit{Fly}(S-\{ i \},b_i+\max(t-a_i,0))|i\in S\rbrace, & S\neq\emptyset\\\ t, & S=\emptyset \end{cases}$$

现在 Fly 给出了一个全集 S={1,2,,n}S=\{1,2,\dots ,n\},和两个长度为 nn 的正整数序列 a,ba,b,他 想知道 Fly(S,0)\mathit{Fly}(S,0) 的值。

a,ba,b 均由「构造参数」生成。给定 xa,ya,zax_a,y_a,z_aaa 的首项 a1a_1,对于 i>1,ai=(ai1×xa+ya)modza+1i>1, a_i=(a_{i-1}\times x_a+y_a)\bmod z_a+1bb 的构造参数及构造方式同理。

输入格式

第一行一个整数 TT,表示数据的组数。

对于每组数据:

  • 第一行一个整数 nn,表示序列的长度也是集合的元素个数;
  • 第二行会给出 44 个正整数 a1,xa,ya,zaa_1,x_a,y_a,z_a
  • 第三行会给出 44 个正整数 b1,xb,yb,zbb_1,x_b,y_b,z_b

输出格式

TT 行,每行一个整数,表示对应的答案。

样例

2
3
3 2 4 5
2 1 1 3
5
7 3 1 7
2 3 2 5
8
20

第一组数据:

aa 序列:3 1 2 bb 序列:2 1 3

第二组数据:

aa 序列:7 2 1 5 3 bb 序列:2 4 5 3 2

数据范围与提示

数据点编号 nn 构造参数
141\sim 4 9\leq 9 100\leq 100
585\sim 8 1000\leq 1000 104\leq 10^4
9169\sim 16 3×105\leq 3\times 10^5 107\leq 10^7
172017\sim 20 2×106\leq 2\times 10^6
对于 100%100\% 的数据,保证 0<T50<T\leq 5n>0n>0,构造参数 >0>0