Cấm Tám

View as PDF

Submit solution

Points: 1.50 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Once upon a time, there were two half-sisters named Cấm and Tám. Cấm's mother passed away early, whereas her father got married to Tám's mother. Cấm's father was a caring person, but unfortunately, he soon was terminally ill, and passed away too. Cấm had to live with her stepmother, who's also Tám's mother. The stepmother was a wicked person, she forced Cấm to do all the hard work every day. For Tám it's the opposite, being nurtured by her mother, Tám never has to do anything, she would go to parties every day, even sometimes she would bully Cấm.

One day, the King opens a huge banquet, inviting all the people of the kingdom to see. Tám and her mother are prepared and eager to go to this banquet. However, not wanting Cấm to be joining with them, they came up with a devilish scheme. The stepmother asked Tám to grab ~n~ jars, numbered from ~1~ to ~n~, the ~i~-th jar containing exactly ~a_i~ grains of rice. When Cấm asked to join the family to the banquet, she poses a task to Cấm, forcing her to measure and separate the rice, such that eventually the ~i~-th jar should contain exactly ~b_i~ grains. Tám and her mother then swiftly went to the banquet, not having a care about Cấm at home, alone with the work.

The task may seem simple, but turns out there are a lot of rice in the jars, so precise measurements is just humanly impossible. Cấm cried out, realizing she was tricked with an impossible task. Hearing her cries, Buddha appeared and asked her what was going on. After hearing her out, Buddha told Cấm to arrange the jars in a circle, such that the first jar is followed by the second jar, the second jar is followed by the third, ..., the ~n~-th jar is followed by the first jar. Buddha then called two birds to help Cấm with her task. The two birds will collaborate together using the following procedure:

  • The first bird picks up any grain of rice from any jar, then moves the grain to the following jar.

  • At the same time, the second bird picks up a different grain of rice from any jar (two birds may pick the same jar), then moves the grain of rice to the preceeding jar.

Moving a single grain of rice may be a slow and tedious action for a human, but for birds, this is easy to perform swiftly, with surgical precision! They can finish the job in no time.

However, knowing how cunning the stepmother is, she might have made it literally impossible to complete the task anyway. Given the initial number of rice grains in each jar, and the target amount, help Cấm and the birds see if it's even possible to complete this task at all. If it's possible, please find the least number of operations that the two birds must perform to complete the task, so that Cấm can get prepared for the great banquet!

Input

There are multiple test cases in each test. The first line contains a single integer ~t~ (~1 \le t \le 100~), the number of tests. Each test case is described as follow.

The first line contains two integers ~n~ and ~k~ (~1 \le n \le 10^5~, ~k \in \{0, 1\}~) the number of rice jars, and the value ~k~ with the following meaning:

  • If ~k = 0~, Cấm just wants to know whether it's actually possible for the two birds to complete the task at all.

  • If ~k = 1~, Cấm also wants to find the least number of moves to complete the task, if it's possible.

See output format for better understanding.

The next line contains ~n~ integers ~a_1, a_2, \ldots, a_n~ (~0 \le a_i \le 10^9~), the number of rice grains in each jar.

The next line contains ~n~ integers ~b_1, b_2, \ldots, b_n~ (~0 \le b_i \le 10^9~), the desired number of rice grains in each jar.

It is guaranteed that the total number of rice jars across all test cases in one test file do not exceed ~10^6~.

Output

For each test case, if it's not possible for the two birds to complete the task, output ~-1~. Otherwise:

  • If ~k = 0~, output any non-negative integer without leading zeros.

  • If ~k = 1~, output the least number of operations it takes to complete the task.

Scoring

  • Subtask 1 (~60~ points): ~n \le 6~, the total number of rice grains within all jars do not exceed ~6~.

  • Subtask 2 (~120~ points): ~k = 0~

  • Subtask 3 (~234~ points): No additional constraints

The total score for this problem is ~414~.

Sample Input 1

5
2 1
2 0
0 2
2 0
2 0
1 1
3 1
1 0 1
1 0 1
3 1
4 1 1
1 1 4
3 0
4 1 1
1 1 4

Sample Output 1

1
-1
0
2
1

Notes

In the first test case, there are only ~n = 2~ jars, and Cấm needs to find the minimum move count. At first, only the first jar contains two grains of rice, we need to move these two grains to the second jar. Two birds can move both these grains to the second jar in one move.

The second test case starts off identical to the first, however the target state now is to make each jar containing one grain of rice. We can see that, the only states reachable are ~[2, 0]~ and ~[0, 2]~, thus it is impossible to satisfy the stepmother's requirement.

In the third test case, the rice amount in each jar already satisfies the target amount, so no operations are needed.

The fourth and fifth test cases are identical, except that the fourth actually requires us to find the minimum move count, whereas the fifth only requires us to check if it's possible. Both cases have ~n = 3~ jars. Initially the rice in the jars are ~[1, 1, 4]~, we want to make it be ~[4, 1, 1]~. The two birds can move as follow:

Step First bird choice Second bird choice Resulting rice amount
(Initially) ~[1, 1, 4]~
1 Jar ~3~ Jar ~3~ ~[2, 2, 2]~
2 Jar ~2~ Jar ~3~ ~[4, 1, 1]~

Fun fact: The story in the statement is based on the Vietnamese folklore Tấm Cám. The story itself bears strong resemblance to the story of Cinderella.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.