Hệ thống giao đồ ăn “ĂnNo” quản lý $N$ cửa hàng giao đồ ăn, đánh số từ $1$ đến $N$. Mỗi cửa hàng có một độ ưu tiên, ban đầu (thời điểm $0$) độ ưu tiên đều bằng $0$.

Sau mỗi $1$ đơn vị thời gian, nếu cửa hàng không có đơn hàng thì độ ưu tiên giảm $1$, thấp nhất giảm đến $0$; còn nếu cửa hàng có đơn hàng thì độ ưu tiên không giảm mà tăng, mỗi đơn hàng làm độ ưu tiên tăng thêm $2$.

Nếu tại một thời điểm nào đó độ ưu tiên của một cửa hàng lớn hơn $5$, cửa hàng đó sẽ được hệ thống đưa vào bộ nhớ đệm ưu tiên; nếu độ ưu tiên nhỏ hơn hoặc bằng $3$, cửa hàng sẽ bị loại khỏi bộ nhớ đệm ưu tiên.

Cho $M$ thông tin đơn hàng trong khoảng thời gian đến $T$, hãy tính tại thời điểm $T$ có bao nhiêu cửa hàng nằm trong bộ nhớ đệm ưu tiên.

Dữ liệu vào

Dòng đầu tiên chứa $3$ số nguyên $N$, $M$ và $T$.

$M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $ts$ và $id$, cho biết tại thời điểm $ts$ cửa hàng số hiệu $id$ nhận được một đơn hàng.

Dữ liệu ra

In ra một số nguyên biểu thị đáp án.

Ví dụ

Input

2 6 6
1 1
5 2
3 1
6 2
2 1
6 2

Output

1

Ghi chú

Giải thích ví dụ

Tại thời điểm $6$, độ ưu tiên của cửa hàng số $1$ giảm xuống $3$, bị loại khỏi bộ nhớ đệm ưu tiên; độ ưu tiên của cửa hàng số $2$ tăng lên $6$, được đưa vào bộ nhớ đệm ưu tiên. Vì vậy có $1$ cửa hàng (cửa hàng số $2$) nằm trong bộ nhớ đệm ưu tiên.

Phạm vi dữ liệu

Với $80\%$ số test, $1 \le N,M,T \le 10000$.

Với tất cả các test, $1 \le N,M,T \le 10^5$, $1 \le ts \le T$, $1 \le id \le N$.

Nguồn: Lanqiao Cup 2019 vòng tỉnh, bảng A bài G.