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.
Sample
| Input | Output |
|---|---|
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 |
