Tí và Tèo chơi trò chơi rải sỏi trên một dãy ~2^k~ ô vuông liên tiếp, các ô vuông này được đánh số theo thứ tự từ ~0~ đến ~2^k - 1~. Ban đầu, các ô vuông này trống. Tí đưa ra thử thách là một dãy ~n~ cặp số ~(c_i, m_i)~, ~i = 1 \dots n~, ~\sum m_i = 2^k~. Tèo cần rải sỏi trên dãy ô vuông này sao cho có ~m_1~ viên sỏi trên mỗi ô vuông trong ~c_1~ ô vuông đầu tiên, có ~m_2~ viên sỏi trên mỗi ô vuông trong ~c_2~ ô vuông tiếp theo, ..., có ~m_n~ viên sỏi trong mỗi ô vuông trong ~c_n~ ô vuông cuối cùng.

Ví dụ: Với ~k = 3, n = 3~, ~(c_1, m_1) = (1,1), (c_2, m_2) = (2,2), (c_3, m_3) = (5,1)~ thì số lượng sỏi trên các ô vuông Tèo cần rải sẽ là ~1, 2, 2, 1, 1, 1, 1, 1~.

Quy tắc rải sỏi như sau: Mỗi lần, Tèo được chọn một đoạn liên tiếp các ô vuông hợp lệ, và rải vào mỗi ô vuông đó ~x~ viên sỏi (~x \le m~), nếu trên những ô vuông này đã có sỏi thì sẽ loại bỏ hết trước khi rải sỏi mới (những lần rải khác nhau thì con số ~x~ này có thể khác nhau).

Một đoạn liên tiếp các ô vuông hợp lệ là một đoạn các ô vuông có chỉ số từ ~L~ đến ~R~ mà ~R - L + 1~ là lũy thừa của 2 (giả sử là ~2^p~) và ~L~ phải là bội của ~2^p~.

Yêu cầu: Hãy tìm số lần rải ít nhất để Tèo có thể rải đúng số sỏi theo yêu cầu của Tí.

Input

• Dòng đầu chứa ba số nguyên ~k, n, m~ (~0 \le k \le 30, 1 \le n \le 10^5, 1 \le m \le 10^9~).
• ~n~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~c_i, m_i~ (~1 \le c_i \le 2^k, 1 \le m_i \le m, \sum c_i = 2^k~).

Output

• Ghi ra một số nguyên duy nhất là số lần rải sỏi ít nhất.