페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#1540

[중등부] 2021 KOI 1차 2교시 실기 대비 모의고사

장비 조합 1초 128MB

문제

정올이는 롤플레잉 게임을 하고 있다. 

이 게임에서 캐릭터는 N개의 장비 슬롯을 가지는데, 각 슬롯에는 하나의 장비만 장착이 가능하다. 

또한 장비는 아무 슬롯에나 장착 할 수 없으며​ 장비마다 정해진 하나의 슬롯에만 장착이 가능하다.

어떤 슬롯은 필수 장착 슬롯으로, q_i 가 1인 경우 i번째 슬롯에는 항상 장비가 장착되어 있어야 한다.​

모든 장비는 1 이상의 정수로 이루어진 [강화레벨] 이라는 값을 가지고 있는데,

캐릭터의 장비 슬롯은 무기 슬롯과 같이 중요한 슬롯이 있고, 장갑 슬롯처럼 덜 중요한 슬롯이 있기 때문에 

캐릭터의 전투력은 각 슬롯의 중요도 wi와 그 슬롯에 장착된 장비 강화레벨의 곱들의 합으로 계산된다. 

예를 들어 1번 슬롯의 중요도가 3, 2번 슬롯의 중요도가 1인 경우, 

1번 슬롯에 강화레벨 3의 장비를 장착하면 전투력 3*3=9를 얻고, 

2번 슬롯에 강화레벨 2의 장비를 장착하면 전투력 1*2=2를 얻게되어

캐릭터의 전투력은 9+2 = 11이 된다.

겁이 많은 정올이는 자신보다 전투력이 낮거나 같은 캐릭터와 전투를 하고 싶다.

정올이의 전투력이 S라고 할 때, 상대방의 전투력이 S이하가 되는 장비 강화레벨 조합이 얼마나 많은지 계산해보자.

[제약 조건]

1 ≤​ N ≤​ 20

0 ≤​ S ≤​ 1,000,000  

1 ≤​ w_i ≤​ 20

0 ≤​ q​_i ≤​ 1


입력

첫 번째 줄에 슬롯의 수 N과 정올이의 전투력 S가 주어진다. 

이후 N개의 줄이 주어지고, 각 i번째 줄에 i번 슬롯의 중요도 w_i와 필수 장착 여부 q_i가 주어진다.

q_i 가 1인 경우 i번째 슬롯은 장비를 꼭 장착해야 하는 슬롯임을 의미한다. 

모​든 입력은 정수 데이터로 주어진다.


출력

첫 번째 줄에 조합의 수를 1,000,000,009로 나눈 나머지를 출력한다.  


부분문제

번호 점수 조건
#110점

N = 1 

#210점

N =​ 2

#320점

N = 3 이면서 S ≤​ 10,000

#420점

N ≤​ 6 이면서 S ≤​ 100​

#540점

추가 제약 조건 없음.​


예제 #1

2 4

1 0

2 0
9

(0,0) (0,1) (0,2) (1,0) (1,1) (2,0) (2,1) (3,0) (4,0) 

괄호안의 값은 (1번 슬롯에 장착된 장비의 강화레벨, 2번 슬롯에 장착된 장비의 강화레벨)

총 9가지 강화레벨 조합이 있다.


예제 #2

2 5

1 0

3 1
3
로그인해야 코드를 작성할 수 있어요.