402376: GYM100739 J Longest cheap palindrome

Memory Limit:64 MB Time Limit:0 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

J. Longest cheap palindrometime limit per test0.25 secondsmemory limit per test64 megabytesinputstandard inputoutputstandard output

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.

Input

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 ≤ 109), 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

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

ExamplesInput
5 2 9
acbba
1 2 10
4 5 11
Output
2
Input
4 2 5
xyyx
3 4 2
2 3 3
Output
4

加入题单

上一题 下一题 算法标签: