Tiệc Buffet của Bessie (Silver)

Có $N$ ô cỏ trong một cánh đồng, mỗi ô có chất lượng $Q_i$ phân biệt. Bessie bắt đầu tại bất kỳ ô nào và có thể di chuyển giữa các ô liền kề, với chi phí $E$ năng lượng mỗi bước.

Khi ăn cỏ ở ô chất lượng $Q$, Bessie nhận được $Q$ năng lượng. Quy tắc: sau khi ăn cỏ chất lượng $Q$, cô chỉ được ăn tiếp ở ô có chất lượng lớn hơn $Q$. Cô có thể đi qua các ô mà không ăn.

Tìm năng lượng tối đa Bessie có thể tích lũy (năng lượng nhận từ ăn cỏ trừ chi phí di chuyển).

Dữ liệu vào

• Dòng đầu: $N$ và $E$
• $N$ dòng tiếp theo: chất lượng $Q_i$, số hàng xóm $D_i$, rồi $D_i$ chỉ số ô hàng xóm

Dữ liệu ra

Năng lượng tối đa Bessie có thể tích lũy.

Ràng buộc

• $1\le N\le 1000$
• $1\le E\le {10}^6$
• $1\le Q_i\le {10}^6$ (các $Q_i$ phân biệt)
• $D_i\le 10$

Ví dụ