Taxi

We all know it’s hard to find an empty taxi in the rush hour of Harbin, so car sharing becomes very common, because the taxi driver can make more money through it. ZB is of money shortage recently, so he gets a part-time job working as a taxi driver.

There are N spots and M passengers in the city, ZB uses an APP called “didi” so he knows everyone’s schedule. Passenger i will take a taxi at exactly t[i] from st[i] to ed[i], and he will pay max(0, pay[i] - travel time). ZB’s taxi can take at most K person one time. He starts in city 1 at time 0.

He is busying driving so will you help him calculate how much can he earn at most?

The first line contains an integer T, meaning the number of the cases.

For each test case:

There are three integers N , M and K in the first line. 1 <= N, M <= 20, 1 <= K <= 4)

Then M lines each contains four integers t[i], st[i], ed[i] and pay[i]. (t[i] < t[i + 1], 1 <= st[i], ed[i] <= n, st[i] != ed[i], 0 <= pay[i] <= 1000)

Then follows by an N * N matrix, the element in the ith row and jth column means the travel time from the ith spot to jth spot. (d[i][j] <= 100, d[i][i] = 0)

For each test case output an integer in a single line --- the most money ZB can earn.