提示: 欢迎访问OurACM平台。
Problem 2217 Taxi

Accept: 5    Submit: 70
Time Limit: 3000 mSec    Memory Limit : 32768 KB

Problem Description

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?

Input

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)

Output

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

Sample Input

3 3 2 1 1 1 3 10 2 2 1 100 0 1 2 1 0 2 2 2 0 2 2 2 2 1 2 100 50 2 1 1000 0 50 50 0 2 2 2 2 1 2 100 50 2 1 1000 0 48 50 0

Sample Output

99 950 1002

Source

第六届福建省大学生程序设计竞赛-重现赛(感谢承办方华侨大学)

Submit  Back  Status  Discuss