25605번 - 입맛이 까다로운 코알라가 유칼립투스 잎을 행복하게 먹을 수 있는 방법

문제

판다는 주식으로 대나무를 먹고, 개미핥기는 주식으로 개미와 흰개미를 먹듯이 코알라는 유칼립투스 잎을 주식으로 먹고 있다.

유칼립투스 잎에는 독성이 있어서 다른 초식동물들은 유칼립투스 잎을 먹지 못하지만, 코알라는 유칼립투스 잎에 있는 독성을 해독할 수 있는 유전자를 지니고 있기 때문에 먹이 경쟁 없이 살아남을 수 있게 되었다.

코알라는 아래의 특징을 가지고 있다.

• 코알라는 유칼립투스 잎을 먹을 때마다 몸 안에 독이 쌓이고, 행복도가 올라가게 된다.
• 코알라는 몸 안에 최대로 축적할 수 있는 독의 최대 한계 용량이 존재하고, 축적되는 독의 양이 최대 한계 용량을 넘어서게 되면 죽게 된다.
• 코알라는 잠을 잘 때마다 일정량의 독을 해독할 수 있다.

항공 동물원에는 코알라가 한 마리 존재한다. 이 코알라는 낮에 유칼립투스 잎을 최대 1개를 먹을 수 있고, 밤에는 무조건 잠을 자는 생활 패턴을 보이고 있다. 그리고 코알라의 입맛은 매우 까다로워서 먹고 싶지 않은 유칼립투스 잎을 보게 된다면 배식통을 엎어버리게 된다.

항공 동물원에서는 코알라에게 아래와 같은 방법으로 유칼립투스 잎을 제공하고 있다.

• 사육사는 배식통에 유칼립투스 잎이 없을 때마다 새로운 유칼립투스 잎을 1개 넣어준다.
• 코알라는 배식통에 있는 유칼립투스 잎을 먹거나, 먹지 않으면 배식통을 엎어버리게 된다.
• 사육사는 코알라가 배식통을 엎어버리면 즉시 배식통에 있던 유칼립투스 잎을 버리고, 새로운 유칼립투스 잎을 배식통에 넣어준다.
• 코알라는 배식통을 하루에 여러 번 엎을 수 있다. 하지만 마지막 유칼립투스 잎이 들어간 배식통을 엎어버리면 사육사는 더 이상 유칼립투스 잎을 주지 않는다.

Koala에서는 항공 동물원에 있는 코알라를 학회 마스코트로 지정하였다. 그리고 학회 마스코트가 된 기념으로 코알라가 죽지 않고 오래 살면서 최대의 행복도를 얻을 수 있도록 유칼립투스 잎을 계획적으로 먹을 수 있는 프로그램을 만들어주려고 한다.

항공 동물원에서 배식통에 넣어주는 유칼립투스 잎의 순서를 알고 있을 때, 이 프로그램을 통해 코알라가 $M$일 동안 유칼립투스 잎을 먹어서 얻을 수 있는 행복도의 최대치를 구하시오.

입력

첫째 줄에 유칼립투스 잎의 개수 $N,ドル 유칼립투스를 먹을 수 있는 기간인 $M$일이 주어진다. $(1 \le N \le 1,000,円 1 \le M \le 100)$

둘째 줄에는 코알라가 몸 안에 축적할 수 있는 독의 최대 한계 용량 $A,ドル 코알라가 하루에 해독할 수 있는 독의 양 $B,ドル 현재 코알라의 몸 안에 축적된 독의 양 $C$가 공백을 두고 주어진다. $(1 \le A \le 100, 0 \le B, C \le A)$

셋째 줄부터 $N$개의 줄에 배식통에 순서대로 넣어주는 유칼립투스 잎에 대한 정보가 주어지는데, 해당 유칼립투스 잎을 먹을 때 코알라 몸 안에 축적되는 독의 양 $x$와 얻을 수 있는 행복도 $y$가 공백을 사이에 두고 주어진다. $(1 \le x \le A, 1 \le y \le 1,000円)$

입력으로 주어지는 모든 값은 정수이다.

출력

$M$일동안 코알라가 얻을 수 있는 행복도의 최대치를 출력한다.

제한

힌트