상남자

CTP의 대표 상남자 영조는 자유롭게 이동하는 것을 좋아한다. 하지만 영조는 상남자이기 때문에 위아래로만 간다. 따라서 위, 아래로는 얼마든지 이동할 수 있지만 왼쪽, 오른쪽으로는 이동하지 않는다. 영조의 행동이 답답한 친구 보성이는 영조가 위, 아래로만 가는 것을 막기 위해 영조와 같이 다니며 왼쪽으로 최대 L번, 오른쪽으로 최대 R번만큼 이동할 수 있게 도와준다. 영조와 보성이는 지도 밖으로는 나가지 않는다.

갈 수 있는 땅, 벽의 위치, 영조와 보성의 출발 위치가 지도 정보로 주어졌을 때 영조와 보성이가 출발 위치로부터 이동해서 갈 수 있는 모든 땅의 개수를 구해보자.

다음은 이해를 돕기 위한 예제 1 그림이다.

영조와 보성이가 시작 위치에서 갈 수 있는 땅은 파란색, 벽이 있어 갈 수 없는 땅은 검은색이다.

다음 그림은 영조와 보성이가 시작 위치에서 왼쪽으로 한 칸 이동했을 때이다.

왼쪽으로 한 칸 이동하였으므로 더 이상 왼쪽으로는 갈 수 없고, 현재 상태에서 갈 수 있는 길은 파란색으로 나타내었다.

다음 그림은 영조와 보성이가 시작 위치에서 아래로 갔을 때이다.

영조와 보성이가 아래로 한 칸 이동했을 때의 갈 수 있는 땅과 현재 상태이다.

다음 그림은 영조와 보성이가 자유롭게 이동하였을 때 도달 가능한 땅을 나타낸다.

영조와 보성이가 최대 왼쪽으로 L번, 오른쪽으로 R번 만큼 움직여서 자유롭게 이동했을 때 도달 가능한 땅은 13칸이다.

첫 번째 줄에 지도의 행과 열 N, M이 주어진다 (1 ≤ N, M ≤ 1,000)

두 번째 줄에 왼쪽과 오른쪽으로 갈 수 있는 최대 횟수 L, R이 주어진다. (0 ≤ L, R ≤ M)

세 번째 줄부터 N+2줄까지 M의 크기만큼 지도가 주어진다.

• 0: 갈 수 있는 땅
• 1: 벽이 있어 갈 수 없는 땅
• 2: 영조와 보성이가 있는 위치

시작 위치를 포함하여 갈 수 있는 땅의 개수를 출력한다.