Một trò chơi ăn bánh quy như sau: Có hai người chơi, chơi luôn phiên nhau. Có một cây gồm đỉnh, tại mỗi đỉnh có đặt số bánh , thời gian để ăn hết một cái bánh tại đây là , thời gian để di chuyển từ đỉnh cha đến nó hoặc ngược lại là , người chơi A đi trước và cố gắng ăn được càng nhiều bánh càng tốt và quay trở lại gốc bằng đường cũ nhưng không được sau thời điểm định sẵn. Người chơi B đi sau và cố gắng ngăn người A ăn được nhiều bánh bằng cách cắt đường đi từ vị trí đỉnh người A đang đứng đến đỉnh con của . Trò chơi sẽ kết thúc khi người A đi xuống đỉnh lá của cây. Lúc đó người A có thể ăn thêm bánh khi quay trở lại gốc của cây theo đường cũ nếu còn thời gian.
Trong trường hợp cả A và B đều chơi tối ưu, thì A có thể ăn được nhiều nhất bao nhiêu cái bánh?
Dữ liệu vào:
Dòng đầu tiên là số và ;
Dòng thứ hai chứa số ;
Dòng thứ ba chứa số ;
Dòng thứ tư chứa số có nghĩa là có cạnh nối trực tiếp đỉnh đến ;
Dòng thứ năm chứa số là thời gian di duyển từ đỉnh đến đỉnh cha của nó và ngược lại.
Dữ liệu ra:
Một số duy nhất là số bánh nhiều nhất mà A có thể ăn được.
Ví dụ:
Dữ liệu vào:
5 26
1 5 1 7 7
1 3 2 2 2
1 1 2 2
1 1 0 0
Dữ liệu ra:
11
Giải thích:
Người A sẽ đi theo đường nếu bị người B chặt cạnh , hoặc nếu bị người B chặt cạnh .
