산타의 선물

산타는 한 가족에게 줄 선물을 가방에 담으려고 한다. 선물의 종류는 $N$가지다. $i$번째 선물 ($1 \le i \le N$)의 크기와 가격은 각각 $s_i$, $p_i$다. 가방의 크기는 $C$이므로 산타는 선물의 총 크기가 $C$를 넘지 않도록 담을 수 있다. 같은 종류의 선물을 여러 개 받으면 아이들이 불행해하므로, 산타는 한 아이에게 같은 종류의 선물을 많아야 하나만 줄 수 있다.

또한 같은 가족의 다른 아이가 받은 선물을 받지 못하면 그 아이는 불평한다. 따라서 산타는 한 가족의 모든 아이에게 선물을 공평하게 나눠 줘야 한다. 즉, 아이가 $k$명인 가족에게는 각 선물 종류마다 0개 또는 $k$개를 담아야 한다. 가방 하나를 한 가족에게 주므로, 한 가족에게 줄 선물의 총 크기도 $C$를 넘지 않는다.

산타는 한 가족에게 담는 선물의 총 가격을 최대로 하고 싶지만, 방문할 가족의 아이 수를 아직 모른다. 그 수는 많아야 $M$명인 것으로 보인다. 가능한 모든 경우에 대비해, 아이가 $k$명인 가족에 대한 최대 총 가격을 각 $1 \le k \le M$에 대해 구하라.

입력은 다음과 같은 형식의 단일 테스트 케이스로 주어진다.

$C$ $N$ $M$
$s_1$ $p_1$
...
$s_N$ $p_N$

첫째 줄에는 세 정수 $C$, $N$, $M$이 주어진다. $C$ ($1 \le C \le 10^4$)는 가방의 크기, $N$ ($1 \le N \le 10^4$)은 선물의 종류 수, $M$ ($1 \le M \le 10^4$)은 가족의 최대 아이 수다. 다음 $N$개 줄의 $i$번째 줄에는 두 정수 $s_i$, $p_i$ ($1 \le s_i, p_i \le 10^4$)가 주어진다. $s_i$와 $p_i$는 각각 $i$번째 선물의 크기와 가격이다.

출력은 $M$개 줄로 이루어진다. $k$번째 줄에는 아이가 $k$명인 가족에 대한 선물의 최대 총 가격을 출력한다.