SCHEDULING TRAINING II$.$

A candidate named Alice is on boarding to Intuit. Intuit demands a required set of traininys to completed. There are $N$ trainings for Alve to compiete. Each of these trainings. has $M$ courses within them which have to be completed. The courses within a training need to be completed in the order they were created. Each course takes time to complete. once you start the course, you CAN pause it and resume it later from the same point.

Alice already has some $P$ prior commitments. She wants to complete all the trainings within $K$ days. Help her determine the order and time in which she can take these trainings, such that she can spend her time in the evening with her friends. Output the minimum time $($of the day$)$ required for her$-$to complete all the trainings. The output can only be an integer value. Example, If the answer $15(3$PM$),$ if Alice spends all the time she has on all $K$ days

ximize

Ss$,$ she would be able to complete

all trainings. Output $-1$ if it is not possible to complete the trainings with her schedule

Constraints

$1T3$

$1N100$

$1M100$

$1P12$

$1K1000$

Input Format

The first line has $T,$ the number of test cases

The second line has $2$ space separated integer $N$ and $M,$ denoting the total number of trainings, and the number of courses within trainings

Next $N$ lines each having $M$ space separated integers, stating the time taken for a course within the training.

Next line denotes the number of prior commitment that Alice has, denoted by $P$

Next $P$ lines contain $2$ space separated integers, stating the starting time and ending

nize

O$.{?}^{{?}^{?}}$ se commitments $(24$ hr scale$)$

Next line contain an integer K$,$ stating the number of days in which Alice needs to complete the trainings

Sample Input

$\backslash$table$[[\{$

$\backslash$table$[[2],[23]]\}],[],[,2],[,1],[4,],[111,],[08,],[141,],[162,2],[4,],[23,],[124,],[212,],[4,],[1112,],[08,],[1418,],[16,23,],[,]]$

Sample Output

$11$

$11$

Explanation

Alice can work from $8-11,12-14$ and $23-24$ hr s$.$ She has $2$ trainings to complete T$1$ and T$2.$

She takes

T$1$ Course$1$ and Course $2$ in Day$18-11,$

T$2$ Course$1$ and Course$2$ on Day$28-11$

T$1$ course $3$ first $3$ hours on day $3-11$

T$1$ course $3$ last $1$ hour on day$48-9$

T$2$ course $3$ on day$49-11.$

She did not take trainings anyday post $11,$ so the answer is $11.$