Description:

一个长度小于700的数列，每个数有三个都是正整数的属性：权值a，删除代价b，附加属性c。

我们要求一个最小代价的删除方案，使得附加属性的字典序最小，并且使新数列权值构成的最长上升序列至少比原数列权值构成的最长上升数列的答案少1

Solution:

我们用dp求出数列的最长上升序列

假如两个点i,j我们可以从i转移到j(即dp[i]=dp[j]-1&&a[i]<a[j])那么我们从i向j连一条边

要让答案t至少减少1，就是要把所有dp[i]=t的点删掉，或者说保留i，但是要把连向i的所有边都断掉

这显然是一个最小割问题。把每个点拆成两个点，之间连b[i]的割代价。可以从i转移到j的点我们连一条(i,j,inf)的边

如果dp[i]为1，连(s,i,inf)如果dp[i]=lis，连(i,t,inf)

这样我们得到了一个分层图，求出最小割就是答案

如何求方案(?)

从小到大枚举c，看这个点能不能被割掉，如果可以那么这个点显然可以加到答案里，我们把它删掉，继续上面的操作

标算是这样的，为了维护删掉点(边)(u,v,z)的新图，我们需要进行退流

退流即从u->s增广z，再从t->v增广z

这样看起来是比删边重建图再跑网络流是要快的

经过一上午的蛋疼的玩常数，结果发现sap的暴力比退流要快很多= =（大概是因为深搜的结果？）

总之比没有玩常数的Drcrow的std要快不少。。

以下一个Ac的暴力程序

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
namespace NSA
{
	const int MAXN = 2010, MAXM = 2000010, inf = MAXM;
	int S, T, tot, cnt, U, times, low, N, M, mx; bool can[MAXN];
	int num[MAXN][MAXN], d[MAXN][MAXN], vector[MAXN][MAXN]; pair<int, int> c[MAXN];
	int vis[MAXN], Answer[MAXN], dp[MAXN], a[MAXN], b[MAXN], Da[MAXN], tod[MAXN];
	struct Eg { int v, z; Eg *ne, *ep; } e[MAXM], *G = e, *po[MAXN], *la[MAXN];
	struct Tbit
	{
		int a[MAXN];
		inline void Init() { for(int i = 1; i <= M; ++i) a[i] = 0; }
		inline void Modify(int x, int y) { for(; x <= M; x += x & -x) a[x] = max(a[x], y); }
		inline int Query(int x) { int ret = 0; for(; x; x -= x & -x) ret = max(ret, a[x]); return ret; }
	} tree;
	inline int read(int &x)
	{
		char ch = getchar(); x = 0;
		for(; ch > '9' || ch < '0'; ch = getchar());
		for(; ch <='9' && ch >='0'; ch = getchar()) x = x * 10 + ch - 48;
		return x;
	}
	inline void add(int a, int b, int c)
	{
		G->v = b; G->z = c; G->ne = po[a]; G->ep = G+1; po[a] = G++;
		G->v = a; G->z = 0; G->ne = po[b]; G->ep = G-1; po[b] = G++;
	}
	inline int dfs(int x, int f)
	{
		if(x == T) return f; int r = 0;
		for(Eg *j = la[x]; j; j = j->ne)
		if(j->z > 0 && d[low][j->v] + 1 == d[low][x])
		{
			la[x] = j; int p = dfs(j->v, min(j->z, f - r));
			j->z -= p; j->ep->z += p; if(f == (r += p)) return r;
		}
		if(d[low][S] >= U) return r;
		if(!--num[low][d[low][x]]) d[low][S] = U;
		++num[low][++d[low][x]]; la[x] = po[x]; return r;
	}
	inline bool Find(int s, int t)
	{
		if(s == t) return 1; vis[s] = times;
		for(Eg *j = po[s]; j; j = j->ne)
			if(j->z > 0 && vis[j->v] != times && Find(j->v, t)) return 1;
		return 0;
	}
	inline void Build()
	{
		mx = 0; tree.Init();
		for(int i = 1; i <= T; ++i) po[i] = 0x0; G = e;
		for(int i = 1; i <= N; ++i) dp[i] = tod[i] = 0;
		for(int i = 1; i <= N; ++i)
		{
			if(!can[i]) add(i, i + N, b[i]);
			mx = max(mx, dp[i] = tree.Query(a[i] - 1) + 1);
			tree.Modify(a[i], dp[i]); vector[dp[i]][tod[dp[i]]++] = i;
			for(int j = 0; j < tod[dp[i] - 1]; ++j)
			{
				int temp = vector[dp[i] - 1][j];
				if(a[temp] < a[i] && !can[i] && !can[temp]) add(temp + N, i, inf);
			}
		}
		for(int i = 1; i <= N; ++i) if(!can[i])
		{
			if(dp[i] ==  1) add(S, i, inf);
			if(dp[i] == mx) add(i + N, T, inf);
		}
	}
	void Solve(int N)
	{
		for(int i = 1; i <= N; ++i) read(a[i]), Da[i] = a[i];
		sort(Da + 1, Da + N + 1); M = unique(Da + 1, Da + N + 1) - (Da + 1);
		for(int i = 1; i <= N; ++i) a[i] = lower_bound(Da + 1, Da + M + 1, a[i]) - Da;
		for(int i = 1; i <= N; ++i) read(b[i]);
		for(int i = 1; i <= N; ++i) read(c[i].first), c[i].second = i;
		S = N * 2 + 1; T = S + 1; U = T;
		for(int i = 1; i <= N; ++i) can[i] = 0; Build();
		for(int i = 1; i <= T; ++i) la[i] = po[i];
		int flow = 0, ans = 0; tot = 0; num[low][0] = U;
		while(d[low][S] < U) flow += dfs(S, inf); ++low;
		sort(c + 1, c + N + 1);
		for(int i = 1; i <= N; ++i)
		{
			Eg *temp = NULL; ++times;
			int x = c[i].second, y = x + N; 
			for(Eg *j = po[x]; j; j = j->ne)
			if(j->v == y) { temp = j; break; }
			if(temp->z || Find(x, y)) continue;
			can[Answer[tot++] = x] = 1; Build();
			for(int i = 1; i <= T; ++i) la[i] = po[i];
			num[low][0] = U; while(d[low][S] < U) dfs(S, inf); ++low;
			if( (ans += b[x]) == flow ) break;
		}
		sort(Answer, Answer + tot); printf("%d %d\n", ans, tot);
		for(int i = 0; i < tot-1; ++i) printf("%d ", Answer[i]); printf("%d\n", Answer[tot-1]);
	}
}
using namespace NSA;
int main()
{
	freopen("lis.in", "r", stdin);
	freopen("lis.out", "w", stdout);
	int TT; for(scanf("%d", &TT); TT--; ) Solve(read(N));
	return 0;
}