HZNUOJ

WXA斗恶龙

Tags:   贪心
Time Limit:  1 s      Memory Limit:   128 MB
Submission:8     AC:4     Score:99.73

Description

LOY被大魔王抓走辣!!
WXA发怒了,要去挑战大魔王。
大魔王有n支护卫队,第i支护卫队里有m_i只恶魔。WXA和恶魔都有攻击力和防御力,当两个角色发生战斗时,若一方的防御力小于另一方的攻击力,则这一方会死亡(存在两边都死亡或两边都存活的情况)。WXA的攻击力是1,恶魔们的防御力全都是0。每当WXA击杀了一只恶魔并且WXA仍存活,WXA的防御力会增加1。当WXA与一支护卫队发生战斗时,WXA会依照护卫队的顺序从前往后依次与恶魔们发生战斗(这是因为恶魔们训练有素,他们总是排成一条竖线冲锋)。恶魔们一共会换防q次,对于第i次换防(x_i,a_i,y_i,b_i),第x_i支护卫队的前a_i只恶魔会与第y_i支护卫队的前b_i只恶魔交换。
你的任务是在每次换防之后,计算出若此时WXA要击杀全部的护卫队恶魔并见到大魔王,至少需要多少点初始防御力。WXA可以决定先与哪支护卫队发生战斗,但必须击杀完一支护卫队才能挑战另一支。

Input

第一行输入一个正整数n(n≥2),表示护卫队数量。
接下来输入n行,第i行输入第一个整数m_i(m_i≥0,∑m_i≥1),接着输入有m_i个空格分隔的整数attack[i,j](1≤attack[i,j]≤100000),表示第i支护卫队按从前往后顺序,第j个恶魔的攻击力。
接下来一行输入一个整数q(q≥1),表示换防次数。
接着输入q行,第i行输入4个整数x_i,a_i,y_i,b_i(x_i≠y_i;1≤x,y≤n;a_i,b_i≥0),表示第i次换防。
其中:n,m_i,q≤1000;∑m_i≤1000;

Output

输出有q行,请在每次换防后,输出若此时WXA要击杀全部的护卫队恶魔并存活,至少需要的初始防御力点数。

Samples

input
2 5 2 5 1 5 6 4 5 6 7 8 3 1 3 2 2 1 4 2 0 1 0 2 5
output
4 5 5

Hint

第一次换防后,第一支护卫队变为 5,6,5,6第二支护卫队变为 2,5,1,7,8若先攻击第一队再攻击第二队,需要 5点防御力。若先攻击第二队再攻击第一队,则只需要4点防御力。

第二次换防后,第一支护卫队没有恶魔了,第二支护卫队变为 5,6,5,6,2,5,1,7,8

第三次换防后,第一支护卫队变为 5,6,5,6,2,第二支护卫队变为 5,1,7,8

Author

WEI, Lixin

Source

计蒜客