Problem Description
Rar the cat has been down on pocket money lately. Therefore, he decided to deliver items in order to earn some extra pocket money. Since Rar the cat has a car capable of holding only up to C items, the delivery company he was working for (Fatdex) has allocated C items for him to deliver for the day.
The items Fatdex allocated to Rar the cat is described using the following 2 integers, D (destination) and M (money earned). This means that Rar the cat would earn $M if he delivers the item to destination D. Rar the cat will start from location 0 and have to end the day at location 0. Due to this, D ≠ 0 for any item and there will be no 2 item with the same D.
The world Rar the cat lives in can be described using a graph with N interconnected nodes and E edges, with places as nodes and labelled from 0 to N-1 (inclusive). Roads will be edges and there will be a total of E edges, each defined as 3 integers, A, B and V, meaning that the distance from place A to place B is Vm.
However, Rar the cat's car also requires fuel to operate (and fuel costs money). The cost of fuel required to travel a road of distance Vm would be $V. Therefore, you are supposed to find the greatest amount of money (net profit) Rar the cat can earn for the day by optimally choosing the items he delivers as well as the path taken! (If he makes a loss by delivering any combination of the items, his maximum net profit would be when he doesn't deliver anything, $0).
Input
You are to input from standard input.
The first line of input consists of 3 integers, C, N, followed by E.
The following C lines of input will consist of D and M, with each line describing 1 item for delivery.
The subsequent E lines of input will consist of A, B followed by V, with each line describing the roads in between places. There will be no 2 roads between A and B (or B and A).
Output
Output a single integer to standard output, denoting Rar the cat's maximum earning for the day.
Limits
For all subtasks:
- 0 < C < N
- 0 ≤ A, B < N
- 0 < V ≤ 10000
- 0 < D < N
- 0 ≤ M ≤ 1000000
Subtask 1 (10%): C ≤ 8, N = C+1, 0 < E ≤ 36
Subtask 2 (18%): C ≤ 8, N ≤ 100, 0 < E ≤ 4950
Subtask 3 (19%): C ≤ 8, N ≤ 10000, 0 < E ≤ 100000
Subtask 4 (23%): C ≤ 13, N ≤ C+1, 0 < E ≤ 91
Subtask 5 (30%): C ≤ 13, N ≤ 10000, 0 < E ≤ 100000
Subtask 6 (0%): As per sample testcases.
Sample Testcase 1
Input:
3 5 6
1 5
3 5
4 25
0 1 3
1 2 2
1 4 9
3 2 1
3 0 2
3 4 5
Output:
17
$17 profit is obtained by choosing to deliver all the items optimally. The cheapest route to deliver all the items and return is 0->1->2->3->4->3->0, which costs $18 ($3+$2+$1+$5+$5+$2). The money earned from making those deliveries is $35 ($5+$5+$25) and thus the net profit is $17 ($35-$18).
Sample Testcase 2
Input:
3 5 6
1 5
3 5
4 5
0 1 3
1 2 2
1 4 9
3 2 1
3 0 2
3 4 5
Output:
2
$2 profit is obtained by choosing to deliver only the first and second item. The cheapest route to deliver them is 0->1->2->3->0, which costs $8 ($3+$2+$1+$2). The money earned from making those deliveries is $10 ($5+$5) and thus the net profit is $2 ($10-$8).
Sample Testcase 3
Input:
3 5 6
1 3
3 8
4 5
0 1 3
1 2 2
1 4 9
3 2 1
3 0 2
3 4 5
Output:
4
$4 profit is obtained by only delivering the second item. The cost for delivery is $4 and the money earned is $8, resulting in a net profit of $4.
Sample Testcase 4
Input:
3 5 6
1 3
3 3
4 5
0 1 3
1 2 2
1 4 9
3 2 1
3 0 2
3 4 5
Output:
0
Making any deliveries will incur a loss to Rar the cat. Therefore, the wisest thing to do is to rest at home and earn $0.
Sample Testcase 5
This testcase adheres to the limits of subtask 4 and 5 only.
Input:
11 12 17
1 3
2 9
3 5
4 3
5 7
6 9
7 10
8 10
9 1
10 5
11 20
9 11 1
9 10 2
9 8 5
9 6 5
8 10 6
8 7 3
8 0 5
8 1 1
1 4 1
2 4 4
2 5 8
0 5 3
0 4 2
5 6 7
6 3 3
7 0 8
7 6 2
Output:
36
By selecting to deliver all items except the 3rd item (D=3, M=5), Rar the cat earns $77. He then delivers these items optimally by going in this order: 0 -$3-> 5 -$8-> 2 -$4-> 4 -$1-> 1 -$1-> 8 -$3-> 7 -$2-> 6 -$5-> 9 -$1-> 11 -$1-> 9 -$2-> 10 -$6-> 8 -$1-> 1 -$1-> 4 -$2-> 0. This results in a fuel cost of $41, which translates to a net profit of $36 ($77-$41). This is the most amount of money Rar the cat can earn for this day. Do note that if Rar the cat decides to deliver all the items, he would earn $1 less than optimal ($35) instead.
Sample Testcase 6
This subtask adheres to the limits of subtask 2, 3 and 5 only.
Input:
7 12 17
1 3
2 9
4 3
6 9
8 10
9 1
10 5
9 11 1
9 10 2
9 8 5
9 6 5
8 10 6
8 7 3
8 0 5
8 1 1
1 4 1
2 4 4
2 5 8
0 5 3
0 4 2
5 6 7
6 3 3
7 0 8
7 6 2
Output:
9
One of the most optimal way to earn the most money is to deliver items 1 (D=1, M=3), 2 (D=2, M=9), 3 (D=4, M=3) and 5 (D=8, M=10) in which Rar the cat would earn $25. However, fuel would cost $16 from taking the path 0 -> 4 -> 1 -> 8 -> 1 -> 4 -> 2 -> 4 -> 0, resulting in the net profit of $9.