Description：

给定序列 $A$ ，第 $i$ 项有删除代价 $B_i$ 和附加属性 $C_i$ ，删除若干项使得 $A$ 的最长上升子序列长度减一，要求付出代价之和最小并输出方案。

$1\leqslant n\leqslant 700$

Solution：

首先不难看出来是一个最小割，如果没有后面那个字典序最小的话就是一个最小费用最大流，考虑怎么求。

我们可以按字典序枚举所有的边，并判断这条边是不是最小割可行边，可行边的条件是 $(u,v)$ 满流并且不存在 $u\to v$ 的增广路径，于是我们就看一看在残量网络上能否从 $u$ 到 $v$ ，如果他是可行边，那么久把他加到集合里，但是这样有一个问题，就是可能会选到一条流上的两条边，于是我们在选完一条边后需要把这条边上的流量去掉，具体做法也很简单，就从 $u\to S,v\to T$ 跑最大流即可，这样经过这条边的所有流都被删掉了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

int n;

#define MAXN 710

int A[MAXN],B[MAXN],C[MAXN];

int id[MAXN];

int f[MAXN];

#define MAXP (MAXN * 2)

#define MAXE (MAXN * MAXN + 3 * MAXN)

struct edge

{

	int to,nxt,f;

}e[MAXE << 1];

int edgenum = 0;

int lin[MAXP] = {0};

void add(int a,int b,int f)

{//cout << a << " " << b << " " << f << endl;

	e[edgenum] = (edge){b,lin[a],f};lin[a] = edgenum++;

	e[edgenum] = (edge){a,lin[b],0};lin[b] = edgenum++;

	return;

}

int S,T;

int s,t;

#define INF 0x3f3f3f3f

int p[MAXN];

int ch[MAXP];

bool BFS()

{

	memset(ch,-1,sizeof(ch));ch[s] = 0;

	queue<int> q;q.push(s);

	while(!q.empty())

	{

		int k = q.front();q.pop();

		for(int i = lin[k];i != -1;i = e[i].nxt)

		{

			if(ch[e[i].to] == -1 && e[i].f)

			{

				ch[e[i].to] = ch[k] + 1;

				q.push(e[i].to);

			}

		}

	}

	return (ch[t] != -1);

}

int flow(int k,int f)

{

	if(k == t)return f;

	int r = 0;

	for(int i = lin[k];i != -1 && f > r;i = e[i].nxt)

	{

		if(ch[e[i].to] == ch[k] + 1 && e[i].f)

		{

			int l = flow(e[i].to,min(e[i].f,f - r));

			e[i].f -= l;r += l;e[i ^ 1].f += l;

		}

	}

	if(r == 0)ch[k] = -1;

	return r;

}

int dinic()

{

	int ans = 0,r;

	while(BFS())while(r = flow(s,INF))ans += r;

	return ans;

}

bool tag[MAXP];

bool BFS(int k,int t)

{

	tag[k] = true;

	if(k == t)return true;

	for(int i = lin[k];i != -1;i = e[i].nxt)

	{

		if(e[i].f == 0 || tag[e[i].to])continue;

		if(BFS(e[i].to,t))return true;

	}

	return false;

}

bool check(int s,int t)

{

	bool res = BFS(s,t);

	memset(tag,false,sizeof(tag));

	return res;

}

void pushflow(int u,int v)

{

	s = u;t = S;

	dinic();

	s = T;t = v;

	dinic();

	return;

}

bool cmp_C(int a,int b){return C[a] < C[b];}

void work()

{

	edgenum = 0;

	memset(lin,-1,sizeof(lin));

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)A[i] = rd();

	for(int i = 1;i <= n;++i)B[i] = rd();

	for(int i = 1;i <= n;++i)C[i] = rd();

	for(int i = 1;i <= n;++i)id[i] = i;

	sort(id + 1,id + 1 + n,cmp_C);

	memset(f,0,sizeof(f));

	for(int i = 1;i <= n;++i)for(int j = 0;j <= i;++j)if(A[j] < A[i])f[i] = max(f[i],f[j] + 1);

	//for(int i = 1;i <= n;++i)cout << f[i] << " ";cout << endl;

	int len = 0;

	for(int i = 1;i <= n;++i)len = max(len,f[i]);

	S = s = 2 * n + 1;T = t = s + 1;

	for(int i = 1;i <= n;++i)add(2 * i - 1,2 * i,B[i]);

	for(int i = 1;i <= n;++i)if(f[i] == 1)add(s,2 * i - 1,INF);

	for(int i = 1;i <= n;++i)if(f[i] == len)add(2 * i,t,INF);

	for(int i = 1;i <= n;++i)for(int j = i + 1;j <= n;++j)

		if(A[i] < A[j] && f[i] + 1 == f[j])add(i * 2,j * 2 - 1,INF);

	int ans1 = dinic();

	int ans2 = 0;

	p[0] = 0;

	for(int i = 1;i <= n;++i)

	{

		int k = id[i];

		if(!check(k * 2 - 1,k * 2))

		{

			++ans2;

			p[++p[0]] = k;

			pushflow(k * 2 - 1,k * 2);

		}

	}

	cout << ans1 << " " << ans2 << endl;

	sort(p + 1,p + 1 + p[0]);

	for(int i = 1;i <= p[0];++i)cout << p[i] << " ";cout << endl;

	return;

}

int main()

{

	int testcases = rd();

	while(testcases--)work();

	return 0;

}