## DMOPC '20 Contest 7 P3 - Senpai and Art

View as PDF

Points: 20 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

It's Senpai's turn to draw now! Senpai starts with an initially empty canvas, represented by an array of length all with layers of paint. In one brush stroke, he can add layer of paint to any subarray of length at least and at most . To allow himself a wide variety of brush strokes, Senpai chooses and such that he can use at least half of all possible stroke lengths from to . In the end, he aims to have exactly layers of paint on index for all . Please tell him the minimum number of brush strokes needed to achieve this, or report that it is impossible. To ensure the integrity of your solution, there may be up to test cases.

#### Constraints

The sum of over all test cases will not exceed .

The sum of over all test cases will not exceed .

#### Input Specification

The first line contains an integer , the number of test cases. The next lines will describe the test cases.

The first line of each test case contains integers , , and .

The second line of each test case contains integers .

#### Output Specification

For each test case, output one integer on its own line: either if it is impossible to get layers of paint on index for all , or the minimum number of brush strokes required to accomplish the task otherwise.

#### Sample Input

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

#### Sample Output

4
-1

#### Explanation

One possible solution for the first test case is to use brush strokes covering the following ranges: .

For the second test case, it can be proven that no sequence of valid brush strokes can get layers of paint on index for all .