국경 통과

Kostya F.는 과세 대상 물품 $n$개를 가지고 어떤 나라의 국경을 넘으려 한다. 각 물품 $i$는 두 정수 $w_i$(무게)와 $c_i$(국경을 넘기 위해 내야 하는 세금)로 나타낸다.

Kostya는 모든 물품을 가방에 나눠 담아야 한다. 가방 수에는 제한이 없다. 각 가방에 든 물품의 무게 합은 $W$를 넘을 수 없다.

세관에는 특별한 규칙이 있다. 세관원은 가방을 열고, 가방의 세금을 안에 든 물품들의 $c_i$ 중 최댓값으로 정한다. 전체 세금은 모든 가방 세금의 합이다.

Kostya가 낼 수 있는 전체 세금의 최솟값과, 그 최솟값을 달성하는 방법의 수를 구하라. 방법의 수는 매우 클 수 있으므로 $998\,244\,353$으로 나눈 나머지를 구한다. 두 분배는 가방 사이에 일대일 대응이 있어서 대응되는 가방이 정확히 같은 물품 집합을 가질 때 같은 것으로 본다.

첫 줄에 두 정수 $n$과 $W$가 주어진다($1 \le n \le 22$; $1 \le W \le 5 \cdot 10^7$).

이어서 $n$개의 줄에 각각 두 정수 $w_i$와 $c_i$가 주어진다($1 \le w_i \le W$; $1 \le c_i \le 5 \cdot 10^7$).

두 정수를 출력한다. 첫 번째는 전체 세금의 최솟값이고, 두 번째는 그 최솟값을 달성하는 방법의 수를 $998\,244\,353$으로 나눈 나머지다.

예시에서 물품은 1부터 5까지 번호가 매겨져 있다. 전체 세금 9를 달성하는 방법은 4가지다.

• [1, 3], [2, 4, 5]: 세금 5 + 4 = 9
• [1, 4], [2, 3, 5]: 세금 5 + 4 = 9
• [1, 5], [2, 3, 4]: 세금 5 + 4 = 9
• [1, 2], [3, 4], [5]: 세금 5 + 3 + 1 = 9