다리 건너기

바이트홀러(Byteholer) 일행이 바이트산맥으로 여행을 떠났다. 그러던 중 눈사태를 일으켰고, 이제 그것을 피해 달아나야 한다. 앞에는 협곡을 가로지르는 낡은 케이블 다리가 있으며, 이들은 최대한 빨리 다리를 건너야 한다. 일행은 아주 가까운 친구 사이여서, 모두 함께 살아남거나 아니면 아무도 살아남지 않기로 정했다.

다리는 오래되고 낡아서 큰 무게를 견디지 못한다. 즉, 어느 순간에도 다리 위에 있는 사람들의 무게 합이 정해진 한계를 넘어서면 안 된다. 또한 케이블 다리이므로 여러 그룹으로 나누어 건너야 한다. 앞선 그룹이 다리를 완전히 벗어난 뒤에야 다음 그룹이 다리에 올라설 수 있다.

각 사람이 다리를 건너는 데 걸리는 시간이 주어진다. 한 그룹의 건너는 시간은 그 그룹에서 가장 느린 사람의 시간과 같고, 전체 건너는 시간은 모든 그룹의 건너는 시간을 더한 값이다. 이 전체 시간은 사람들을 그룹으로 어떻게 나누느냐에 따라 달라진다.

다음을 수행하는 프로그램을 작성하라.

• 표준 입력에서 다리와 사람들에 대한 정보를 읽는다,
• 모든 사람이 다리를 건너는 데 필요한 전체 시간의 최솟값을 구한다,
• 그 값을 표준 출력에 쓴다.

첫째 줄에 두 정수가 공백 하나로 구분되어 주어진다. $W$는 다리가 견딜 수 있는 최대 무게 합이고 ($100 \le W \le 400$), $n$은 사람 수이다 ($1 \le n \le 16$).

이어지는 $n$개의 줄에는 각 사람을 나타내는 두 정수가 공백 하나로 구분되어 주어진다. $t$는 그 사람이 다리를 건너는 데 걸리는 시간이고 ($1 \le t \le 50$), $w$는 그 사람의 무게이다 ($10 \le w \le 100$).

모든 사람이 다리를 건너는 데 필요한 전체 시간의 최솟값을 정수 하나로 출력한다.