Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Rainy Day

Limits 1s, 512 MB

You have to complete N tasks tomorrow, where each task can last for any number of minutes. Each task must be performed in the given order and multiple tasks can not be performed at the same time.

However, tomorrow’s weather forecast predicts that it would be a very rainy day and all of your tasks involve going outside. You are given the predictions of when rain can occur as a list of time duration. You want to schedule the tasks, such that you can minimize working on the rain.

Find the minimum time you need to work in the rain. It is guaranteed that all tasks can be finished within a day.

Input

First line contains a single integer, T (1 ≤ T ≤ 100), number of test cases.

Each test case starts with a single line with two integers, N (1 ≤ N ≤ 100) and M (1 ≤ M ≤ 100), representing number of tasks and number of rain predictions respectively.

Next line contains N integers representing duration of all the tasks in minutes.

Next M lines contains descriptions of M rain predictions n any order.

Each rain prediction is given in the form of h1:m1-h2:m2, where h1, m1 represents the starting time of rain (hours and minutes) and h2:m2 represents ending time of rain. Note that, both starting time and ending time are inclusive. The time is given in 24:00 hour format and can range from 0:0 to 23:59.

Output

For each test case, output a single integer representing the minimum duration you need to work in the rain to complete all the tasks.

Samples

InputOutput
3
3 2
10 20 30
0:0-12:00
12:40-23:40
2 1
60 60
1:0-23:00
1 3
300
12:00-23:59
0:0-7:59
8:0-8:59
11
1
120


Discussion
Submit

Login to submit