차원 디버깅

이 문제 하나를 며칠째 붙잡고 씨름해 왔고, 이제 더는 못 참겠다. 알고리즘의 버그를 이번에는 반드시 찾아내기로 했다. 그래서 처음부터 다시 시작한다. 완전히 새로 말이다. 가장 단순한 경우의 정답은 확실히 안다. $(0,0,\dots,0)$에 대한 답은 $0$이다.

k개의 매개변수를 받는 문제를 n개의 더 단순하지만 느린 알고리즘으로 다시 푼다. 각 알고리즘은 모든 매개변수 $i$마다 두 개의 경계 $L_i$와 $H_i$를 가진다. 알고리즘은 모든 매개변수 $i$에 대해 $x_i \leq H_i$를 만족하는 입력 $(x_1,\dots,x_k)$에서만 제 속도로 실행된다. 알고리즘 구현이 올바르다고 확신하려면, 모든 매개변수 $i$에 대해 $x_i \geq L_i$를 만족하는 입력 $(x_1,\dots,x_k)$에서 정확성을 적어도 한 번 검증해야 한다. 이를 위해서는 정확성이 이미 증명되어 있고 그렇게 큰 입력을 처리할 수 있는 다른 알고리즘이 필요하다. 또는 $(0,0,\dots,0)$의 답을 알고 있어야 한다.

알고리즘들과 각각의 경계가 주어질 때, 올바르게 구현되었다고 확신할 수 있는 알고리즘의 개수를 구하라.

예를 들어 그림 D.1 왼쪽의 첫 번째 샘플을 보자. 첫 번째 알고리즘(빨강, 왼쪽 아래)으로 두 번째 알고리즘(노랑, 왼쪽 위)과 세 번째 알고리즘(파랑, 오른쪽 아래)의 정확성을 검증할 수 있다. 네 번째 알고리즘(회색, 오른쪽 위)의 정확성을 검증할 수 있는 알고리즘은 없다.

그림 D.1: 샘플 1과 2에서 각각 테스트할 알고리즘. 상자는 알고리즘을 테스트해야 하는 매개변수를 나타내고, 밝은 배경은 해당 알고리즘이 다른 알고리즘을 검증하는 데 쓰일 수 있는 영역을 나타낸다.

입력은 다음과 같다.

• 첫 줄에 정수 $n$과 $k$가 주어진다 ($1\leq n\leq 1000$, $1\leq k\leq 10$). 테스트할 알고리즘의 개수와 매개변수의 개수이다.

• 이어서 $n$쌍의 줄이 주어진다.

  • 한 줄에 $k$개의 정수 $L_1, \dots, L_k$가 주어진다 ($0\leq L_i \leq 10^9$).
  • 한 줄에 $k$개의 정수 $H_1, \dots, H_k$가 주어진다 ($0\leq H_i \leq 10^9$).

• 모든 $i$에 대해 $L_i \leq H_i$가 보장된다.

정확성을 검증할 수 있는 알고리즘의 개수를 출력한다.