펀드 운용

Frank는 폐쇄형 주식형 펀드를 운용한다. 펀드는 투자자들로부터 c 달러를 모아 m일 동안 운용하며, 기간이 끝나면 보유한 모든 주식을 다시 현금으로 바꾼다. Frank는 거래할 n개의 종목을 선택했다.

각 종목에는 고정된 한 로트(lot)의 크기 s_i(한 로트에 포함된 주식 수)가 있다. 주가가 주당 p 달러인 날에 종목 i를 한 로트 매수하면 p · s_i 달러가 들며 펀드의 현금이 줄어든다. 주가가 p인 날에 한 로트를 매도하면 p · s_i 달러를 받아 펀드의 현금이 늘어난다. 한 로트를 거래하면 하루가 온전히 소요되므로, Frank는 하루에 최대 한 가지 행동만 할 수 있다: 한 로트 매수, 한 로트 매도, 또는 아무것도 하지 않기. 한 로트 전체를 살 만큼 현금이 없으면 매수할 수 없으며, 로트를 쪼개어 살 수는 없다.

위험을 제한하기 위해, 어느 시점에나 종목 i는 최대 k_i 로트까지, 그리고 모든 종목을 합쳐 최대 k 로트까지만 보유할 수 있다. 펀드는 시작할 때와 마찬가지로 마지막 날에도 현금만 보유해야 한다(매수한 모든 로트는 마지막 날까지 매도되어야 한다).

모든 종목의 매일 주가를 미리 알고 있을 때, m일이 끝난 뒤 펀드가 보유할 수 있는 현금의 최댓값을 구하라.

각 종목은 하루에 하나의 주가로 매수·매도가 이루어진다고 가정하며, 수수료나 커미션은 모두 무시한다.

첫째 줄에 c m n k가 주어진다.

• c (0.01 ≤ c ≤ 100000000.00) — 모은 현금으로, 센트 단위(소수점 아래 최대 두 자리)까지 주어진다.
• m (1 ≤ m ≤ 100) — 운용 일수.
• n (1 ≤ n ≤ 8) — 종목 수.
• k (1 ≤ k ≤ 8) — 어느 시점에나 보유할 수 있는 전체 로트 수의 상한.

이어서 종목을 설명하는 2n개의 줄이 종목마다 두 줄씩 주어진다.

• 각 종목의 첫째 줄에는 종목 이름과 두 정수 s_i, k_i가 주어진다. s_i (1 ≤ s_i ≤ 1000000)는 한 로트의 크기이고, k_i (1 ≤ k_i ≤ k)는 이 종목을 어느 시점에나 보유할 수 있는 최대 로트 수이다. 종목 이름은 1~5개의 대문자 알파벳(A–Z)으로 이루어지며 모두 서로 다르다.
• 각 종목의 둘째 줄에는 공백으로 구분된 m개의 주가가 주어지며, 각 날의 주가이다. 각 주가는 0.01 이상 999.99 이하이고 센트 단위까지 주어진다.

현금과 주가는 십진수 숫자 뒤에 선택적으로 소수점과 한두 자리의 소수 부분이 붙는 형식이다.

m일이 끝난 뒤 펀드가 보유할 수 있는 현금의 최댓값을 한 줄에 출력한다. 정수부(달러), 점, 그리고 센트를 나타내는 정확히 두 자리 숫자 형식으로 출력한다(예: 151205.00). 정답은 1000000000.00을 넘지 않는다.