A series of highways connect `n` cities numbered from `0` to `n - 1`. You are given a 2D integer array `highways` where `highways[i] = [city1i, city2i, tolli]` indicates that there is a highway that connects `city1i` and `city2i`, allowing a car to go from `city1i` to `city2i` and **vice versa** for a cost of `tolli`.

You are also given an integer `k`. You are going on a trip that crosses **exactly** `k` highways. You may start at any city, but you may only visit each city **at most** once during your trip.

Return _the **maximum** cost of your trip. If there is no trip that meets the requirements, return_ `-1`_._

**Example 1:**

**Input:** n = 5, highways = \[\[0,1,4\],\[2,1,3\],\[1,4,11\],\[3,2,3\],\[3,4,2\]\], k = 3
**Output:** 17
**Explanation:**
One possible trip is to go from 0 -> 1 -> 4 -> 3. The cost of this trip is 4 + 11 + 2 = 17.
Another possible trip is to go from 4 -> 1 -> 2 -> 3. The cost of this trip is 11 + 3 + 3 = 17.
It can be proven that 17 is the maximum possible cost of any valid trip.

Note that the trip 4 -> 1 -> 0 -> 1 is not allowed because you visit the city 1 twice.

**Example 2:**

**Input:** n = 4, highways = \[\[0,1,3\],\[2,3,2\]\], k = 2
**Output:** -1
**Explanation:** There are no valid trips of length 2, so return -1.

**Constraints:**

*   `2 <= n <= 15`
*   `1 <= highways.length <= 50`
*   `highways[i].length == 3`
*   `0 <= city1i, city2i <= n - 1`
*   `city1i != city2i`
*   `0 <= tolli <= 100`
*   `1 <= k <= 50`
*   There are no duplicate highways.


def dfs(curr_city, remaining_highways, cost_so_far, highways, visited):
    if remaining_highways == 0:
        return cost_so_far

    visited[curr_city] = True
    max_cost = -1

    for highway in highways:
        next_city = -1
        if highway[0] == curr_city and not visited[highway[1]]:
            next_city = highway[1]
        elif highway[1] == curr_city and not visited[highway[0]]:
            next_city = highway[0]

        if next_city != -1:
            cost = dfs(next_city, remaining_highways - 1, cost_so_far + highway[2], highways, visited)
            max_cost = max(max_cost, cost)

    visited[curr_city] = False
    return max_cost


def max_cost(n, highways, k):
    visited = [False] * n
    max_cost = -1

    for i in range(n):
        cost = dfs(i, k, 0, highways, visited)
        max_cost = max(max_cost, cost)

    return max_cost
