Read problems statements in Russian also. 
Chef likes playing with strings. The most interesting game are named "CHEF in string". The move of the game consists of the following: Chef takes a subsequence of string's letters that form the word "CHEF" and then he removes that symbols. The goal of the game is to make the maximal number of moves. Please, help Chef and tell him the maximal possible number of moves that he is able to make for the given string S.

------ Input ------ 

The first line of each test case contains a given string. This string consists of uppercase letters from the set {"C", "H", "E", "F"}. 

------ Output ------ 

Output a single line containing the maximal possible number of moves.

------ Constraints ------ 

$1  ≤ |S| ≤ 100000$

------ Scoring ------ 

Subtask 1 (25 points): |S| ≤ 2000 

Subtask 2 (75 points):  See the constraints. 

----- Sample Input 1 ------ 
CHEFCHEFFFF

----- Sample Output 1 ------ 
2
----- explanation 1 ------ 
- In the first move, Chef can pick the subsequence $[1, 2, 3, 4]$. Thus the characters at these indices are C, H, E, and F. Chef removes this subsequence. The remaining string is CHEFFFF.
- In the second move, Chef can pick the indices $[1, 2, 3, 4]$ of the remaining string CHEFFFF as the subsequence. The characters at these indices are C, H, E, and F. Chef removes this subsequence. The remaining string is FFF.
- Chef cannot make any more valid moves.

----- Sample Input 2 ------ 
CHHHEEEFFCC
----- Sample Output 2 ------ 
1
----- explanation 2 ------ 
- In the first move, Chef can pick the subsequence $[1, 2, 5, 8]$. Thus the characters at these indices are C, H, E, and F. Chef removes this subsequence. The remaining string is HHEEFCC.
- Chef cannot make any more valid moves.

Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Constructive algorithms

Ad-hoc
Skill types: Dynamic programming

Starter code:

Solutions:
s = input()
c1 = c2 = c3 = c4 = 0
for i in range(len(s)):
	if s[i] == 'C':
		c1 += 1
	if s[i] == 'H':
		c2 += 1
		c2 = min(c2, c1)
	if s[i] == 'E':
		c3 += 1
		c3 = min(c2, c3)
	if s[i] == 'F':
		c4 += 1
		c4 = min(c3, c4)
print(c4)


s = input()
c = 0
h = 0
e = 0
f = 0
for _ in s:
	if _ == 'C':
		c += 1
	elif _ == 'H' and c > h:
		h += 1
	elif _ == 'E' and h > e:
		e += 1
	elif _ == 'F' and e > f:
		f += 1
res = min([c, h, e, f])
print(res)


s = input()
(c, h, e, f) = (0, 0, 0, 0)
for ch in s:
	if ch == 'C':
		c += 1
	elif ch == 'H':
		if c > h:
			h += 1
	elif ch == 'E':
		if h > e:
			e += 1
	elif e > f:
		f += 1
print(f)


s = input()
(c, h, e, f) = (0, 0, 0, 0)
for i in s:
	if i == 'C':
		c += 1
	elif i == 'H' and c > h:
		h += 1
	elif i == 'E' and h > e:
		e += 1
	elif i == 'F' and e > f:
		f += 1
print(f)


from math import *
import sys

def input():
	return sys.stdin.readline().replace('\n', '').strip()
sys.setrecursionlimit(10 ** 9)

def bin_search(el, lst):
	if lst == []:
		return -1
	if lst[0] > el:
		return -1
	else:
		low = 0
		high = len(lst) - 1
		while low <= high:
			mid = (low + high) // 2
			if el < lst[mid]:
				high = mid - 1
			else:
				low = mid
			if high - low == 1:
				if lst[high] < el:
					return high
				return low
			if low == high:
				return low
		return low
s = input()
n = len(s)
c = []
h = []
e = []
f = []
ans = 0
for i in range(n):
	if s[i] == 'C':
		c.append(i)
	elif s[i] == 'H':
		if c != []:
			h.append(i)
	elif s[i] == 'E':
		if h != []:
			e.append(i)
	elif s[i] == 'F':
		if e != []:
			f.append(i)
			f_ind = -1
			e_ind = bin_search(f[f_ind], e)
			if e_ind != -1:
				h_ind = bin_search(e[e_ind], h)
				if h_ind != -1:
					c_ind = bin_search(h[h_ind], c)
					if c_ind != -1:
						ans += 1
						del c[c_ind]
						del h[h_ind]
						del e[e_ind]
						del f[f_ind]
print(ans)


a = list(input())
c = h = e = f = 0
for x in a:
	if x == 'C':
		c = c + 1
	elif x == 'H' and h < c:
		h = h + 1
	elif x == 'E' and e < h:
		e = e + 1
	elif x == 'F' and f < e:
		f = f + 1
print(f)


s = input()
c = ch = che = chef = 0
for i in range(0, len(s)):
	if s[i] == 'C':
		c += 1
	elif s[i] == 'H':
		if c > 0:
			c -= 1
			ch += 1
	elif s[i] == 'E':
		if ch > 0:
			ch -= 1
			che += 1
	elif s[i] == 'F':
		if che > 0:
			che -= 1
			chef += 1
print(chef)


from sys import stdin, stdout
input = stdin.readline
s = input().strip()
n = len(s)
arr1 = [i for i in range(n) if s[i] == 'C']
arr2 = [i for i in range(n) if s[i] == 'H']
arr3 = [i for i in range(n) if s[i] == 'E']
arr4 = [i for i in range(n) if s[i] == 'F']
(i, j, k, l) = (0, 0, 0, 0)
(a, b, c, d) = (len(arr1), len(arr2), len(arr3), len(arr4))
count = 0
while i < a:
	while j < b and arr2[j] <= arr1[i]:
		j += 1
	if j == b:
		break
	while k < c and arr3[k] <= arr2[j]:
		k += 1
	if k == c:
		break
	while l < d and arr4[l] <= arr3[k]:
		l += 1
	if l == d:
		break
	count += 1
	i += 1
	j += 1
	k += 1
	l += 1
print(count)


n = input()
c = 0
h = 0
e = 0
f = 0
for i in n:
	if i == 'C':
		c += 1
	elif i == 'H' and c > h:
		h += 1
	elif i == 'E' and h > e:
		e += 1
	elif i == 'F' and e > f:
		f += 1
v = min([c, h, e, f])
print(v)


s = input().upper()
(a, b, c, d) = (0, 0, 0, 0)
for i in s:
	if i == 'C':
		a += 1
	if i == 'H' and a > 0:
		if a > b:
			b += 1
	if i == 'E' and b > 0:
		if b > c:
			c += 1
	if i == 'F' and c > 0:
		if c > d:
			d += 1
print(min(a, b, c, d))


string = input()
c = 0
h = 0
e = 0
f = 0
for _ in string:
	if _ == 'C':
		c += 1
	elif _ == 'H' and c > h:
		h += 1
	elif _ == 'E' and h > e:
		e += 1
	elif _ == 'F' and e > f:
		f += 1
v = min([c, h, e, f])
print(v)


s = input()
n = len(s)
c = c1 = c2 = c3 = 0
for i in range(0, n):
	if s[i] == 'C':
		c = c + 1
	elif s[i] == 'H' and c > 0:
		c1 = c1 + 1
		c = c - 1
	elif s[i] == 'E' and c1 > 0:
		c2 = c2 + 1
		c1 = c1 - 1
	elif s[i] == 'F' and c2 > 0:
		c3 = c3 + 1
		c2 = c2 - 1
print(c3)


a = input()
c = 0
ch = 0
che = 0
chef = 0
for letter in a:
	if letter == 'C':
		c += 1
	elif letter == 'H' and c > 0:
		ch += 1
		c -= 1
	elif letter == 'E' and ch > 0:
		che += 1
		ch -= 1
	elif letter == 'F' and che > 0:
		chef += 1
		che -= 1
print(chef)


s = input()
d = {'C': 0, 'H': 0, 'E': 0, 'F': 0}
for i in s:
	if i == 'H':
		d[i] = min(d['C'], d[i] + 1)
	elif i == 'E':
		d[i] = min(d['C'], d['H'], d[i] + 1)
	elif i == 'F':
		d[i] = min(d['C'], d['H'], d['E'], d[i] + 1)
	elif i == 'C':
		d[i] += 1
print(d['F'])


import sys, math
sys.setrecursionlimit(10 ** 5)

def pro(arr):
	n = len(arr)
	(c, chef, ch, che) = (0, 0, 0, 0)
	ans = 0
	for i in range(n):
		if arr[i] == 'C':
			c += 1
		if arr[i] == 'H':
			if c:
				ch += 1
				c -= 1
		if arr[i] == 'E':
			if ch:
				che += 1
				ch -= 1
		if arr[i] == 'F':
			if che:
				chef += 1
				che -= 1
	print(chef)
n = list(input())
pro(n)


s = input()
arr = [0] * 4
for i in s:
	if i == 'C':
		arr[0] += 1
	elif i == 'H' and arr[0] > arr[1]:
		arr[1] += 1
	elif i == 'E' and arr[1] > arr[2]:
		arr[2] += 1
	elif i == 'F' and arr[2] > arr[3]:
		arr[3] += 1
print(arr[3])


str1 = str(input())
c = h = e = f = 0
for i in str1:
	if i == 'C':
		c += 1
	elif i == 'H' and c > h:
		h += 1
	elif i == 'E' and h > e:
		e += 1
	elif i == 'F' and e > f:
		f += 1
print(min(c, h, e, f))


ctest = str(input())
ccount = {'C': 0, 'CH': 0, 'CHE': 0, 'CHEF': 0}
for i in range(len(ctest)):
	if ctest[i] == 'C':
		ccount['C'] += 1
	elif ctest[i] == 'H' and ccount['C'] > ccount['CH']:
		ccount['CH'] += 1
	elif ctest[i] == 'E' and ccount['CH'] > ccount['CHE']:
		ccount['CHE'] += 1
	elif ctest[i] == 'F' and ccount['CHE'] > ccount['CHEF']:
		ccount['CHEF'] += 1
print(ccount['CHEF'])


class Solution:

	def solve(self):
		self.solve_each()

	def solve_each(self):
		s = input()
		n = len(s)
		count = 0
		search_s = 'CHEF'
		search_dic = dict(((c, idx) for (idx, c) in enumerate(search_s)))
		dp = dict()
		for c in s:
			idx = search_dic[c]
			if not idx:
				dp[idx] = dp.get(idx, 0) + 1
				continue
			if dp.get(idx - 1, 0):
				dp[idx] = dp.get(idx, 0) + 1
				dp[idx - 1] -= 1
		print(dp.get(3, 0))

def main():
	sol = Solution()
	sol.solve()
main()


s = input().lower()
(a, b, c, d) = (0, 0, 0, 0)
for i in s:
	if i == 'c':
		a += 1
	if i == 'h' and a > 0:
		if a > b:
			b += 1
	if i == 'e' and b > 0:
		if b > c:
			c += 1
	if i == 'f' and c > 0:
		if c > d:
			d += 1
print(min(a, b, c, d))


s = input().lower()
count = 0
(c, h, e, f) = (0, 0, 0, 0)
for i in s:
	if i == 'c':
		c += 1
	if i == 'h' and c > 0:
		if c > h:
			h += 1
	if i == 'e' and h > 0:
		if h > e:
			e += 1
	if i == 'f' and e > 0:
		if e > f:
			f += 1
print(min(c, h, e, f))


S = list(input())
c = 0
ch = 0
che = 0
ans = 0
for i in range(len(S)):
	if S[i] == 'C':
		c += 1
	elif S[i] == 'H':
		if c > 0:
			c -= 1
			ch += 1
	elif S[i] == 'E':
		if ch > 0:
			ch -= 1
			che += 1
	elif S[i] == 'F':
		if che > 0:
			ans += 1
			che -= 1
print(ans)


try:
	S = list(input())
	c = h = e = f = 0
	for i in S:
		if i == 'C':
			c += 1
		elif i == 'H' and h < c:
			h += 1
		elif i == 'E' and e < h:
			e += 1
		elif i == 'F' and f < e:
			f += 1
	print(f)
except:
	pass


t = input()
c = h = e = f = a = b = res = 0
length = len(t)
for i in range(length):
	if t[i] == 'C':
		c += 1
	elif t[i] == 'H' and c > h:
		h += 1
	elif t[i] == 'E' and h > e:
		e += 1
	elif t[i] == 'F' and e > f:
		f += 1
a = min(e, f)
b = min(h, a)
res = min(c, b)
print(res)
t = ''


S = input()
cArr = 0
chArr = 0
cheArr = 0
result = 0
for i in range(len(S)):
	if S[i] == 'C':
		cArr += 1
	elif S[i] == 'H' and cArr >= 1:
		chArr += 1
		cArr -= 1
	elif S[i] == 'E' and chArr >= 1:
		cheArr += 1
		chArr -= 1
	elif S[i] == 'F' and cheArr >= 1:
		result += 1
		cheArr -= 1
print(result)