Cow Water Slide – Maximizing Guaranteed Fun

Farmer John has built a giant water slide for the cows inspired by the new water park at Machu Picchu. The slide comprises V pools (numbered 1 to V) and E directed mini slides. Each mini slide i goes from pool P_i to pool Q_i and provides fun value \(F_i\). The cows always start at pool 1 and ride until they reach pool V. Every pool (except pool 1) has at least one incoming slide and every pool (except pool V) has at least one outgoing slide.

Since the ride is long, the cow Bessie wants to maximize her fun. However, due to her cow nature, she may lose control up to K times. At a pool where she loses control, an adversary chooses the outgoing slide for her – i.e. she obtains the worst (minimum) outcome at that pool. When she is in control she picks the outgoing slide that is most beneficial. Note that a losing control event can happen at any pool including pool 1.

If we let \(dp(u, k)\) be the maximum fun that Bessie can guarantee when starting at pool \(u\) with at most \(k\) loss-of-control events remaining, the recurrences are as follows:

• For the last pool \(V\): \(dp(V, k)=0\) for all \(k\).
• For \(k=0\) (no loss-of-control possible): \[ dp(u,0)=\max_{(u\rightarrow v)} \Bigl(F + dp(v,0)\Bigr). \]
• For \(k \ge 1\): Let \[ A = \max_{(u\rightarrow v)} \Bigl(F + dp(v,k)\Bigr) \quad\text{and}\quad B = \min_{(u\rightarrow v)} \Bigl(F + dp(v,k-1)\Bigr). \] Then \[ dp(u,k)=\min(A, B). \] This is because when in control Bessie can secure at most \(A\) fun, but if she loses control the adversary forces her to take the worst slide resulting in fun \(B\). In either case she is guaranteed at least \(\min(A,B)\).

Your task is to compute the maximum guaranteed fun Bessie can achieve starting at pool 1 with K possible loss-of-control events.

Input Format (see below):

• The first line contains three integers: V (number of pools), E (number of mini slides), and K (maximum loss-of-control events).
• Then follow E lines, each containing three integers: P_i, Q_i, and F_i representing a mini slide from pool P_i to pool Q_i with fun value F_i.

Output Format: Print a single integer: the maximum guaranteed fun Bessie can achieve.

inputFormat

The first line contains three integers V, E, and K.

Each of the next E lines contains three integers: P_i, Q_i and F_i.

outputFormat

Output a single integer representing the maximum fun Bessie is guaranteed to achieve.

sample

3 4 1
1 2 5
1 3 9
2 3 5
2 3 3

9