지원 도구의 동시 점검

문제

한 회사의 사내 IT 지원팀은 직원용 컴퓨터에 배포하는 지원 도구들을 점검하려 한다. 점검 대상 도구는 N개이며, 각 도구에는 1번부터 N번까지 서로 다른 번호가 붙어 있다. 지원팀은 이번 점검에 사용할 컴퓨터 한 대를 확보했다. 도구마다 점검 환경을 준비하는 데 필요한 저장 공간이 정해져 있고, 이 컴퓨터에서 점검에 사용할 수 있는 저장 공간은 B이다. 지원팀은 정확히 K개의 도구를 골라 점검 환경을 준비하려 한다. 선택한 도구들의 필요 공간을 모두 더한 값이 B 이하여야 한다. 필요 공간이 같은 도구라도 번호가 다르면 서로 다른 도구이며, 각각 독립적으로 선택할 수 있다. 공간을 나누어 사용하거나 도구 하나를 여러 번 선택하는 것은 허용하지 않는다. 저장 공간만 확인해서는 안 된다. 일부 도구 쌍은 같은 설정 파일을 서로 다른 방식으로 수정하므로, 같은 컴퓨터에 점검 환경을 함께 준비할 수 없다. 이러한 관계가 M개의 충돌 쌍으로 주어진다. 충돌 쌍에 포함된 두 도구 중 하나만 선택하는 것은 가능하지만, 둘을 모두 선택하는 것은 불가능하다. 충돌 관계는 입력에 주어진 쌍에만 적용된다. 예를 들어 1번과 2번이 충돌하고 2번과 3번이 충돌하더라도, 1번과 3번이 별도의 충돌 쌍으로 주어지지 않았다면 둘을 함께 선택할 수 있다. 지원팀은 조건을 만족하는 도구 선택 방법이 몇 가지인지 알고 싶다. 선택한 도구 번호의 집합이 같으면 선택 순서와 관계없이 같은 방법으로 센다. 정확히 K개를 선택하고, 필요 공간의 합이 B 이하이며, 어떤 충돌 쌍도 동시에 선택하지 않는 방법의 수를 구한다. 가능한 방법이 없으면 0을 출력한다. K가 0이면 아무 도구도 선택하지 않는 방법 하나가 있으며, 이 방법의 필요 공간은 0이다.

입력

첫째 줄에 정수 N, K, B, M이 공백으로 구분되어 주어진다. 1 ≤ N ≤ 20, 0 ≤ K ≤ N, 0 ≤ B ≤ 20,000, 0 ≤ M ≤ N(N-1)/2이다.
둘째 줄에 각 도구의 필요 공간을 나타내는 정수 A_1, A_2, ..., A_N이 주어진다. 모든 i에 대해 1 ≤ A_i ≤ 1,000이다.
다음 M개 줄에는 충돌하는 두 도구의 번호 u, v가 주어진다. 1 ≤ u < v ≤ N이며, 같은 충돌 쌍은 중복해서 주어지지 않는다. M이 0이면 충돌 쌍을 나타내는 줄은 없다.

출력

조건을 만족하는 도구 선택 방법의 수를 정수 하나로 출력한다. 가능한 방법이 없으면 0을 출력한다.

4 2 7 2
2 3 4 5
1 2
3 4

3

3 2 3 0
2 2 2

0

3 0 0 2
7 7 7
1 2
2 3

1

출처: Devin.KR 자체 제작