J. Longest cheap palindrome
time limit per test
0.25 seconds
memory limit per test
64 megabytes
input
standard input
output
standard 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.

Examples
Input
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