方阵

题目限制

1500 ms 512 M

题目描述

给定一个 $n\times n$ 的数字方阵，其中第 $i$ 行为长度 $n$ 的序列 $A_{i,1},A_{i,2},...,A_{i,n}$。

对于集合 $S$，定义 $mex(S)$ 为 $S$ 中没有出现的最小的自然数，如：$mex(\{ 0\} )=1, mex(\{ 1, 2\} )=0$。

对于序列 $A_i$ 的所有区间，设 $f_i$ 为其中第 $k$ 小的 $mex$ 值。

给定权值序列 $w_1,w_2, ... ,w_n$，求 $max\{ f_i+w_i\}$。

注意：

为减小输入量，每行的序列 $A_i$ 采用如下方式随机生成：

给出四个数 $k_i,w_i,m,seed$，$k_i,w_i$ 为上述题意中的参数，$m$ 为序列值的上界，$seed$ 为随机种子。之后执行以下程序：

int n,k,w,m,A[N];
unsigned long long seed;
unsigned long long _rand(){
    seed^=seed<<13;
    seed^=seed>>7;
    seed^=seed<<17;
    return seed;
}
void read_test(){
    scanf("%d%d%d%llu",&k,&w,&m,&seed);
    for(int i=1;i<=n;++i) A[i]=_rand()%m;
}

输入格式

第一行输入一个正整数n，描述方阵的规模； 之后n行，每行4个数ki,wi,m,seed，描述一行随机生成的序列。 其中1≤m≤n≤10000,k≤n(n+1)/2。

输出格式

输出一个数，表示max{fi+wi}。

数据范围

对于10%的数据，$n\le 100$；

对于30%的数据，$n\le 1000$；

另有20%的数据，$m\le 5$；

对于100%的数据，$n\le 10^4, 1\le m\le n, k\le n(n+1)/2, w_i\le 10^9, 0\le seed\le UNSIGNED\_LONG\_LONG\_MAX$。

输入样例

4
4 3 3 1
6 2 2 2
4 0 4 3
3 1 3 4

输出样例

4