Informatica Online Judge

  달리기 [0215 / 00D7]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 115   Total Tried : 129


The Champion of this Problem (C++) : tlsdydaud1 - 0ms / 138byte
My Best Submission (C++) : N/A

[]

Background

베시는 다음 시합을 위해 달리기 연습 중이다. 베시는 그 어떤 환경에도 적응할 수 있도록 언덕을 포함한 코스에서 훈련 중이다. 베시는 직선 코스를 계획하고 있으며 가능한 한 멀리 뛰고자 한다.

하지만 M초(1 ≤ M ≤ 10,000,000) 안에는 농장으로 돌아와야 한다. 베시가 선택한 전체 코스 길이는 T유닛(1 ≤ T ≤ 100,000)이며 오르막, 평지, 내리막은 동일한 길이로 구성되어 있다.

입력 데이터는 각 코스 길이 i를 하나의 기호 Si로 표현하며 이것은 오르막(u), 평지(f), 내리막(d)을 나타낸다. 베시는 U초 동안 오르막 코스, F초 동안 평지 코스, D초 동안 내리막 코스를 달리게 된다.

집으로 돌아올 때에는, 오르막은 내리막이 되고 내리막은 오르막이 된다는 것을 주의하라. 베시가 농장에서 출발하여 가장 멀리 갈 수 있는 거리를 구하시오. 단, 제 시간 안에 돌아와야 한다.

Input

* 첫 번째 줄은 공백(스페이스)로 구분된 5개의 정수 M, T, U, F, D가 온다.
* 두 번째 줄부터 T+1줄까지에서 i+1줄은 경로 i를 하나의 알파벳 Si로 나타낸다.

Output

* 첫 번째 줄은 베시가 농장에서 출발하여 제 시간 안에 돌아올 수 있는 가장 먼 거리를 나타내는 정수이다.

IO Example

입력
13 5 3 2 1
u
f
u
d
f

출력
3

출처 : USACO (http://ace.delos.com)

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]