样例下载

【题目描述】

有 n 个男生，m 个女生，现在要将他们排成一队。

一个队列是否是和谐的，我们用“和谐度”来表示。

初始时，队列的和谐度为 1。然后我们通过以下规则统计一个队列的和谐度：

• 每有连续的 a 个男生，并且下一个人仍然是男生，则和谐度 +1。例如，若 a=5，且连续有 12 个男生，则队列的和谐度 +2。（连续的 x 个男生可使得队列所增加的和谐度为 ⌊(x-1)/a⌋，其中 ⌊⌋ 表示下取整）

• 每有连续的 b 个女生，并且下一个人仍然是女生，则和谐度 +1。（连续的 x 个女生可使得队列所增加的和谐度为 ⌊(x-1)/b⌋）

• 每有两个异性相邻，则队列的和谐度 +1。

另外，队伍要求：对于任意一段非结尾的连续的女生，人数不能少于 c。

问：能得到的队列和谐度最大可能是多少？

多组数据。

【输入格式】

第一行：一个整数 T 表示数据组数。

接下来 T 行，每行代表一组数据，包含 5 个整数，依次为 n, m, a, b, c，含义如上所述。

【输出格式】

共 T 行，每行一个整数表示对应数据的答案。

【样例输入】

6 
1 1 1 1 1 
5 4 3 3 2 
5 5 3 3 2 
3 9 3 3 3 
7 3 3 5 8 
4 7 2 8 5 

【样例输出】

2 
5 
6 
8 
4 
5 

【样例说明】

用 A 表示男，用 B 表示女，则：

第 1 组数据可以排列为 AB 或者 BA，和谐度为 2。

第 2 组数据可以排列为 ABBAAAABB，也可以排列为 ABBAAABBA，和谐度均为 5。

第 3 组数据可以排列为 ABBABBAAAB，和谐度为 6。

第 4 组数据可以排列为 ABBBBABBBBAB，和谐度为 8。

第 5 组数据可以排列为 AAAAAAABBB，和谐度为 4。

第 6 组数据可以排列为 AAABBBBBABB，和谐度为 5。

【数据范围】

对于 20% 的数据，有 1 ≤ T ≤ 5, 1 ≤ n, m, a, b, c ≤ 10

对于 50% 的数据，有 1 ≤ T ≤ 50, 1 ≤ n, m, a, b, c ≤ 100

对于 100% 的数据，，有 1 ≤ T ≤ 50, 1 ≤ n, m, a, b, c ≤ $10^5$