402376: GYM100739 J Longest cheap palindrome

Given a string S of length N, you must find the longest palindromic substring of even length. This sounds like a simple problem, but wait, there's more to it. You also have a budget of B coins and R restrictions that may affect it. For example, a restriction of shape (a, b, c) means that given the case you decided to include in your substring all characters from position a to b in your string S, you must pay c coins. Given the budget and a set of restrictions, output the size of the longest palindromic substring of even length that can be formed.

On the first line there are 3 integers, N (1 ≤ N ≤ 33), the length of the string, R (1 ≤ R ≤ 5000), the number of restrictions and B (1 ≤ B ≤ 10⁹), the budget. On the second line you can find string S. Next R lines contain three numbers: a, b, and c describing a restriction.

Output a single number, the maximal length of the palindromic substring.

5 2 9
acbba
1 2 10
4 5 11

2

4 2 5
xyyx
3 4 2
2 3 3

4