def coin_chain(s: str, tourists: list[tuple[str, int]]):
    def coin_chain_recur(s):
        nonlocal tourists, profit, result
        if len(s) == 0:
            result = max(result, profit)
            return
        for i in range(len(tourists)):
            substr, price = tourists[i]
            substr_i = s.find(substr)
            if substr_i == -1:
                continue
            profit += price
            s_trunc = s[:substr_i] + s[substr_i+len(substr):]
            coin_chain_recur(s_trunc)
            coin_chain_recur(s_trunc[::-1])
            profit -= price

        result = max(result, profit)
        return

    result = float('-inf')
    profit = 0
    coin_chain_recur(s)
    coin_chain_recur(s[::-1])
    return result