Taco Travel Time Optimization

You are given several test cases. In each test case, there are m stations. You are provided with two lists that describe the journey between consecutive stations:

• A list of m-1 integers where each integer represents the distance between consecutive stations.
• A list of m-1 integers where each value is either 0 or 1. A value of 0 indicates that the segment is traveled at normal speed, while a value of 1 indicates fast speed.

When traveling at normal speed, the time needed to traverse a segment is exactly equal to the distance. For a segment with fast speed, the time required is \(\lceil \frac{d}{2} \rceil\) where \(d\) is the distance for that segment and \(\lceil \cdot \rceil\) denotes the ceiling function.

Your task is to compute the minimum travel time for each test case.

inputFormat

The input is read from standard input (stdin). The first line contains an integer \(T\) representing the number of test cases. The description of each test case is as follows:

• The first line contains an integer \(m\) (the number of stations).
• The second line contains \(m-1\) integers representing the distances between consecutive stations.
• The third line contains \(m-1\) integers where each integer is either 0 or 1. A 0 indicates normal speed while a 1 indicates fast speed.

outputFormat

For each test case output a single line that contains the minimum travel time required to complete the journey showing the total time computed as per the rules described above. The output is printed to standard output (stdout).

## sample

3
3
4 2
1 0
4
5 10 4
0 1 1
2
7
1

4
12
4

</p>