Nhân dịp sinh nhật cô bò Bessie, Farmer John cho cô toàn quyền ăn cỏ trên một trong những cánh đồng tốt nhất của ông.

Cánh đồng có \(N\) bãi cỏ (\(1 \le N \le 1000\)), được đánh số thuận tiện từ \(1 \ldots N\), và mỗi bãi có một giá trị chất lượng phân biệt. Nếu Bessie ăn cỏ có chất lượng \(Q\), cô nhận được \(Q\) đơn vị năng lượng. Mỗi bãi cỏ được nối với không quá 10 bãi lân cận bằng các đường đi hai chiều, và Bessie tốn \(E\) đơn vị năng lượng để di chuyển giữa hai bãi kề nhau (\(1 \le E \le 1{,}000{,}000\)). Bessie có thể chọn bắt đầu gặm cỏ tại bất kỳ bãi nào và muốn dừng lại khi đã tích lũy được lượng năng lượng lớn nhất.

Không may, Bessie là một cô bò kén chọn: sau khi ăn cỏ có một mức chất lượng nhất định, cô sẽ không bao giờ ăn cỏ có chất lượng bằng hoặc thấp hơn mức đó nữa! Cô vẫn sẵn lòng đi qua các bãi mà không ăn cỏ ở đó; thực tế, cô có thể thấy việc đi qua một bãi cỏ chất lượng cao mà không ăn, rồi quay lại sau để thưởng thức, là có lợi.

Hãy xác định lượng năng lượng lớn nhất Bessie có thể tích lũy.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(E\). Mỗi dòng trong \(N\) dòng còn lại mô tả một bãi cỏ. Dòng đó chứa hai số nguyên \(Q\) và \(D\), lần lượt cho biết chất lượng của bãi cỏ (nằm trong khoảng \(1 \ldots 1{,}000{,}000\)) và số bãi lân cận của nó. \(D\) số còn lại trên dòng cho biết các bãi lân cận.

Dữ liệu ra

In lượng năng lượng lớn nhất Bessie có thể tích lũy.

Ví dụ

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

7

Nguồn

USACO 2015 US Open, Silver — Bessie's Birthday Buffet. Tác giả đề: Austin Anderson và Brian Dean, 2015.

https://usaco.org/index.php?page=viewproblem2&cpid=551