把 Bob 的出拳看成三类:出 0、出 1、出 2,分别计数为 cntB[0..2]。
Alice 手里分别有 a 个 0、b 个 1、c 个 2(总和等于 n)。
胜负规则是:1 胜 0,2 胜 1,0 胜 2。
为了让胜场最大,显然应当把 Alice 能赢的对局尽量“按类型匹配”:
min(cntB[0], b) 场;min(cntB[1], c) 场;Alice 与 Bob 进行 n 回合猜拳,出拳用数字表示:0、1、2,其中 1 打败 0 ,2 打败 1,0 打败 2 (其他情况视为 Alice 不胜)。
你已知 Bob 接下来每一回合的出拳序列。Alice 事先准备了 a 个 0、b 个 1、c 个 2 (保证 a+b+c=n ),每回合必须恰好出一拳,且各拳种的使用次数分别不超过 a,b,c 。
请你在这些限制下,合理安排 Alice 每一回合的出拳顺序,使得赢的回合数最大,并输出最多能赢的回合数。
每个测试文件均包含多组测试数据。第一行输入一个整数 T(1≤T≤105) 代表数据组数,每组测试数据描述如下:
第一行输入一个整数 n(1≤n≤105) 。
第二行输入 n 个整数 s1,...,sn(si∈{0,1,2}).表示 Bob 每回合的出拳。
第三行输入三个整数 a,b,c , 表示 Alice 拥有的 0,1,2 的数量,保证 a+b+c=n 。
保证所有测试中 n 的总和不超过 2×105 。
输出 T 行,每行一个整数,表示在最优安排下 Alice 最多能赢的回合数。
输入
3
5
0 1 2 0 1
2 2 1
3
2 2 2
3 0 0
4
0 1 2 2
1 1 2
输出
4
3
3