불꽃놀이

Cverker PlusPlusson는 매년 새해를 성대한 불꽃놀이로 기념한다. 2015 동안 예산의 대부분을 컴퓨터, 게임 콘솔, 그리고 대왕고래 모양 봉제 인형에 쓰고 나니, 이번에는 공연을 성대하게 만들기가 평소보다 어렵다는 사실이 드러났다.

하나의 공연은 여러 개의 불꽃으로 구성되며, 불꽃의 종류는 $N$가지이다. $i$ 유형을 Cverker가 구매하는 데에는 $P_i$크로나가 든다. 관객을 즐겁게 하려면 공연이 성대하고 다채로워야 한다. $i$ 유형의 로켓 하나를 발사하면 공연의 성대함에 $S_i$만큼 기여하며, 성대한 공연에서는 발사한 로켓들의 성대함의 합이 적어도 $M$이어야 한다. 공연이 다채로우려면 같은 로켓을 너무 자주 반복해서는 안 된다. 더 구체적으로, 어떤 로켓도 전체 발사 횟수의 절반 이상 사용되어서는 안 된다.

Cverker가 공연 비용을 최소화할 수 있도록 공연 설계를 도와라.

첫 번째 줄에는 불꽃 유형의 수와 공연에 필요한 성대함을 나타내는 두 정수 $N$와 $S$가 주어진다($3 \le N \le 20$, $1 \le S \le 200$).

다음 $N$개의 줄에는 각각 두 정수가 주어진다. $i$번째 줄에는 정수 $1 \le S_i \le 200$와 $1 \le P_i \le 200$가 주어진다.

불꽃놀이의 최소 비용을 나타내는 정수 하나를 출력한다.