시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 256 MB 77 15 9 13.043%

문제

17세의 호반우가 길을 건너간다는 특성이 있다면 15세의 호반우에게는 중2병이 찾아온다는 특성이 있다!

중2병에 걸린 호반우들은 인간들을 호반우빔으로 죽이는 망상을 자주 한다.

그들이 하는 망상의 내용은 구체적으로 이러하다.

  1. 감옥은 N × M 크기의 격자판으로 이루어져 있고 감옥에는 사람 한 명이 갇혀있다.
  2. 사람들은 호반우 도축, 호반우 감금, 호반우 우권 침해 셋 중 하나의 죄명을 가지고 있다.

호반우는 호반우빔을 사용해 이 사람들을 죽일 계획을 가지고 있다..!!

사람들은 호반우빔에 맞게되면 탈모가 생기며 빠른 시간안에 죽는다.

호반우빔은 격자 모양의 감옥 왼쪽 경계 혹은 위쪽 경계에서 격자와 평행한 방향으로만 발사할 수 있다.

발사한 호반우빔은 격자를 순서대로 관통해서 반대쪽 경계까지 도달한다.

따라서, 왼쪽에서 오른쪽으로 가는 호반우빔을 발사하거나 위쪽에서 아래쪽으로 가는 호반우빔을 발사할 수 있는 것이다.

호반우는 죽이기만 하면 재미없으니까 죽일 때 마다 점수를 계산하는데 호반우 도축자를 죽이면 1명당 a점, 호반우 감금자를 죽이면 1명당 b점을 얻게 되고 호반우 우권 침해자를 죽이면 앞으로 얻을 점수가 c배가 된다.

호반우는 최대한 많은 점수를 얻고 싶었지만 안타깝게도 호반우는 사칙 연산을 할 줄 모른다.

호반우를 위해 호반우가 얻을 수 있는 최소 점수와 최대 점수를 알려주자!

입력

첫 번째 줄에 N, M, a, b, c (1 ≤ NM ≤ 10, -100 ≤ a, b ≤ 100, -2 ≤ c ≤ 2) 가 공백으로 구분되어 주어진다. 

2번째 줄부터 N+1번째 줄 까지는 격자의 정보가 공백으로 구분되어 주어진다.

각 칸별로

0인 경우 사람이 존재하지 않는 감옥

1인 경우 호반우 도축을 저지른 사람

2인 경우 호반우 감금을 저지른 사람

3인 경우 호반우 우권 침해를 저지른 사람이다.

호반우 우권 침해자는 항상 20명 이하이다.

출력

문제에서 설명한 최솟값과 최댓값을 공백으로 구분하여 순서대로 출력한다.

예제 입력 1

2 3 2 1 2
2 3 1
1 0 2

예제 출력 1

0 12


예제에 나온 격자판을 그려보면 위 그림과 같다.

호반우빔을 발사할 수 있는 위치는 빨간색 원으로 그려진 총 5개의 위치에서 발사할 수 있다.

4번 위치에서 발사하는 경우, 2 3 1을 순서대로 관통한다.

이렇게 관통하는 경우 진행과정은 아래와 같다.

  1. b값이 1이므로 1점을 얻게 된다.
  2. c값이 2이므로 앞으로 얻을 점수가 2배가 된다.
  3. a값이 2이므로 2 × 2 = 4점을 얻게 된다.
  4. 관통된 후 격자에 있는 사람은 죽었다. (격자의 값이 0이 된다.)

이 경우는 설명을 돕기 위한 예시로 예제의 답과는 상관없다. 

예제 입력 2

1 3 1 1 2
1 3 1

예제 출력 2

0 4

예제 입력 3

1 3 -1 -1 2
3 3 1

예제 출력 3

-4 0

노트

호반우가 모든 사람을 죽이지 않아도 된다.

출처

University > 경북대학교 > 2020 Goricon K번