拒绝挂科
题号:NC25185
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

进入大学,我们每学期都需要经历期末考试,而如果我们平时不认真学习,仅靠前几小时进行复习,则可能会不慎挂科并且重修所挂科目。若我们所挂的科目过多则会受到学校降级甚至退学的处罚。

某学校的处罚制度如下:

1.正常情况下,一个学生在校学习时间为 n 年;若出现降级、休学等特殊情况,学生将则在校学习时间将不得超过 m(1<=n<=m<=2e5)年,若学习时间超出 m 年无法正常毕业。

2.学校不设置补考,若期末考试不及格将在明年的该学期重修该科目;重修科目的考试将在该学期正常期末考试之前进行;挂科数量结算在每个学期所有科目的考试出分之后。

3.正常情况下,一个学生在第i年秋季/春季学期需要学习的科目数量为s[i*2] /a[i*2+1](1<=s[i*2]<=1e9);若出现降级、休学等特殊情况,则该年所学科目将延后一年学习。

3.若在第 i 年秋季/春季学期若某学生连续挂科达到 a[i*2]/a[i*2+1]

(1<=a[i*2]<=1e9),则对该学生将受到降级处分;例如:若某同学 2018 年春季学期无挂科,2018 年秋季学期挂科 2 科,2019 年春季学期挂科 3 科,无论在 2018 年之前该同学未通过科目总数为多少,该同学连续挂科数量 5 科。

4.若在第 i 年秋季/春季学期若某学生累计挂科达到 b[i*2]/b[i*2+1]

(1<=b[i*2]<=1e9),则对该学生将受到退学处分,无法正常毕业。

5.降级、休学学生将不再学习任何课程或进行任何科目的考试,并且在最近的一个秋季学期重新学习过去一年所挂科目和未完成学习的科目并进行重修考试和期末考试。

现在我们想计算我们在大学期间至多能挂多少不同的科目,能够保证大学能够正常毕业?

输入描述:

输入数据第一行包括一个整数t,表示输入数据共有t(1<=t<=10)组;对于每组输入第一行包括两个整数n和m;第二行包括s数组,共n*2个数字顺序表示从入学到毕业正常情况下每个年级两个学期需要学习的科目数量;第三行包括a数组,共m*2个数字顺序表示从入学到最晚毕业年限m年每个年级两个学期可连续挂科而不降级最大数量;第三行包括b数组,共m*2个数字顺序表示从入学到最晚毕业年限m年每个年级两个学期可累计挂科而不退学最大数量。

输出描述:

对于每组输入,输出一行,包括一个整数,表示大学期间至多能挂的不同科目的数量。
示例1

输入

复制
2
1 2
4 5
10 10 10 10
11 12 13 14
2 3
2 2 2 3
5 5 6 6 7 7
6 6 7 7 8 8

输出

复制
9
9