숨겨진 연필꽂이

시간 제한1초메모리 제한1024 MB

요약

N행 M열 격자에 케이스 높이가 주어지고 길이 H인 연필이 있을 때, 연필을 넣었을 때 어느 옆면에서 수직으로 봐도 보이지 않는 케이스의 개수를 센다.

난이도: 보통10점 중 5점
유형: 배열, 구현, 시뮬레이션, 완전 탐색
정답자: 아직 제출이 없습니다

문제

그림 A

연필을 연필보다 짧은 꽂이에 넣으면 그림 A처럼 연필이 보인다. 이제 여러 개의 꽂이를 모아 한 묶음으로 만들자. 이 중에서 연필을 넣었을 때 연필이 보이지 않는 꽂이들을 골라낼 수 있을까? (그림 B를 보라)

그림 B (예시를 나타낸다)

이 문제에는 N개의 행과 M개의 열로 이루어진 연필꽂이 묶음이 주어진다. 꽂이들은 모두 단면이 정사각형이고 크기가 같으며, 서로 빈틈없이 붙어 있고 아래쪽 끝이 탁자에 닿아 있다. 꽂이들의 높이는 서로 다를 수 있다. 각 꽂이의 높이와 연필의 길이 H를 알 때, 묶음의 옆면 어느 위치에서든 시선이 묶음의 수직 벽에 수직이 되도록 바라볼 때 연필이 보이지 않도록 연필을 넣을 수 있는 꽂이의 개수를 구하라.

입력

첫째 줄에서 N, M, H를 읽는다. 다음 N개 줄 각각에서 왼쪽에서 오른쪽 순서로 그 행에 있는 꽂이들의 높이를 읽는다. 모든 값은 200 이하의 양의 정수이다.

출력

표준 출력의 한 줄에 답이 되는 꽂이의 개수를 출력한다.

힌트

설명: 예시 입력에서 회색으로 표시된 칸은 연필을 넣었을 때 연필이 보이지 않는 꽂이를 나타낸다.

예제1

예제 1
입력
```
3 4 5
7 7 4 4
6 3 7 3
6 7 6 2
```
예상 출력
```
8
```