Cho $2$ mảng $a$ và $b$ gồm $n$ phần tử gồm các số nguyên không âm và số nguyên dương $k$.

Ở mỗi thao tác bạn có quyền chọn $1$ số có giá trị $i$ $(1 \leq i \leq n)$ sau đó hoán đổi giá trị $a_{i}$ và $b_{i}$.

Nhiệm vụ của bạn là tìm số thao tác nhỏ nhất để $\sum_{i=1}^{n} a_{i}$ có giá trị bằng $j$ (với $j$ là các số tự nhiên từ $1$ đến $k$).

Input

• Dòng đầu tiên gồm số $n$ và $k$ $(1 \leq n, k \leq 10^{5})$.
• Trong $n$ dòng tiếp theo, dòng thứ $i$ chứa $2$ số $a_{i}$ và $b_{i}$ $(1 \leq \sum_{i = 1}^{n} (a_{i} + b_{i}) \leq 2 \times 10^{5})$.

Output

• Gồm $k$ dòng, dòng thứ $j$ in ra số lượng thao tác ít nhất để $\sum_{i=1}^{n} a_{i}$ có giá trị bằng $j$, nếu không tồn tại cách nào thì in ra $-1$.

Scoring

• Subtask $1$ ($50\%$ số điểm): $1 \le n, k \le 2000, 1 \le \sum_{i =1}^{n} (a_{i} + b_{i}) \le 2000$.
• Subtask $2$ ($50\%$ số điểm): Không có rằng buộc gì thêm.

Example

3 5
1 3
2 5
0 7

-1
-1
0
-1
1