Ở TLEOJ Cup năm nay, các thành viên của câu lạc bộ TLE tổ chức trao thưởng cho những thí sinh có thành tích xuất sắc bằng một trò chơi nhỏ. Trò chơi diễn ra trên một lưới gồm \(n\) hàng và \(m\) cột. Ô ở hàng \(i\), cột \(j\) được ký hiệu là \((i,j)\). Có \(k\) ô chứa quà; ô thứ \(t\) nằm tại \((x_t,y_t)\) và có \(v_t\) phần quà.

Người chơi bắt đầu ở một ô bất kỳ trên hàng thứ nhất và thực hiện đúng \(n\) bước. Ở mỗi bước:

• Nếu ô hiện tại có quà, người chơi nhận tất cả quà trong ô đó.
• Nếu đang ở ô \((i,j)\) với \(i<n\), người chơi có thể đi đến một trong các ô

miễn là ô đích nằm trong lưới.

• Nếu \(i=n\), trò chơi kết thúc.

Hãy tìm số phần quà tối đa người chơi có thể nhận.

Xem các hình minh họa đường đi của ví dụ trong đề PDF chính thức.

Input

• Dòng đầu chứa bốn số nguyên không âm \(n,m,k,d\) (\(1 \le n,m \le 10^9\), \(0 \le k \le \min(nm,2\cdot10^5)\), \(0 \le d < m\)).
• \(k\) dòng tiếp theo, dòng thứ \(t\) chứa ba số nguyên dương \(x_t,y_t,v_t\), cho biết ô \((x_t,y_t)\) có \(v_t\) phần quà (\(1 \le x_t \le n\), \(1 \le y_t \le m\), \(1 \le v_t \le 10^9\)).
• Các vị trí \((x_t,y_t)\) đôi một phân biệt.

Output

• In ra một số nguyên là số phần quà tối đa có thể nhận.

Example

2 4 2 2
2 1 1
2 2 2

2

4 5 4 1
3 2 1
4 1 1
1 5 2
2 2 1

3

1 3 2 0
1 2 1000000000
1 1 1000000000

1000000000

Scoring

• \(5\%\) số điểm: \(k \le 2\).
• \(5\%\) số điểm: \(d=0\).
• \(10\%\) số điểm: \(n,m \le 15\) và \(d=1\).
• \(10\%\) số điểm: \(n,m \le 200\).
• \(10\%\) số điểm: \(n,m \le 1000\).
• \(10\%\) số điểm: \(n,m \le 5000\).
• \(15\%\) số điểm: \(k \le 5000\).
• \(15\%\) số điểm: \(d=1\) và \(v_i=1\).
• \(10\%\) số điểm: \(d=1\).
• \(10\%\) số điểm: không có ràng buộc gì thêm.