알고리즘을 좋아하는 나

Mickey의 뒷마당에는 특정 수의 양이 있다. 그가 단단히 잠든 사이에 배고픈 늑대는 마당에 들어와 양을 공격했다.

마당은 정사각형 모양에 행과 열로 이루어진 필드이다. 글자 '.' (점)은 빈 필드를 의미하며, 글자 '#'는 펜스를, 글자 'o'는 양, 'v'는 늑대를 의미한다.

우리는 수평, 수직으로만 이루어지고 펜스가 없는 경로에 한하여 한 필드에서 다른 필드로 이동할 수 있다면 같은 영역이라고 간주한다. 우리가 "탈출"할 수 있는 영역은 그 어떠한 영역의 부분으로도 간주하지 않는다.

다행히 우리의 양은 카라테 검은 띠 보유자여서 늑대에게 싸움을 걸 수 있고 영역에 늑대의 수보다 많다면 이기게 된다. 그렇지 않다면 그 지역 안의 모든 양을 먹는다.

맨 처음 모든 양과 늑대는 마당 안 영역에 존재한다.

아침이 도달했을 때 아직 살아남은 양과 늑대의 수를 출력하는 프로그램을 작성하라.

첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다.

R개의 줄은 C개의 글자를 가진다. 이들 모두는 마당의 구조(마당의 펜스, 양, 늑대의 위치)를 의미한다.

참고: 50%의 입력은 간단한 구조로, 모든 영역은 직사각형 형태를 가지고 영역 내에 펜스가 없다.

오직 하나의 줄에 아침까지 살아있는 양과 늑대의 수를 의미하는 두 정수를 출력한다.

개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 번갈아가면서 등장한다.

아래 그림은 길이가 14미터이고 높이가 5미터인 동굴이다. (예제 그림)

이 개똥벌레는 장애물을 피하지 않는다. 자신이 지나갈 구간을 정한 다음 일직선으로 지나가면서 만나는 모든 장애물을 파괴한다.

위의 그림에서 4번째 구간으로 개똥벌레가 날아간다면 파괴해야하는 장애물의 수는 총 여덟개이다. (4번째 구간은 길이가 3인 석순과 길이가 4인 석순의 중간지점을 말한다)

하지만, 첫 번째 구간이나 다섯 번째 구간으로 날아간다면 개똥벌레는 장애물 일곱개만 파괴하면 된다.

동굴의 크기와 높이, 모든 장애물의 크기가 주어진다. 이 때, 개똥벌레가 파괴해야하는 장애물의 최소값과 그러한 구간이 총 몇 개 있는지 구하는 프로그램을 작성하시오.

첫째 줄에 N과 H가 주어진다. N은 항상 짝수이다. (2 ≤ N ≤ 200,000, 2 ≤ H ≤ 500,000)

다음 N개 줄에는 장애물의 크기가 순서대로 주어진다. 장애물의 크기는 H보다 작은 양수이다.

첫째 줄에 개똥벌레가 파괴해야 하는 장애물의 최소값과 그러한 구간의 수를 공백으로 구분하여 출력한다.