Vào dịp Tết Nguyên Đán tại vùng đất cổ Đại Việt, người dân có phong tục đi trẩy hội, viếng thăm các ngôi đền thiêng để cầu bình an và tài lộc cho năm mới. Tương truyền rằng, vùng đất này có ngôi đền linh thiêng, được đánh số từ đến . Ngôi đền số là Đền Tổ, nơi khởi nguồn của mọi mạch khí.
Mỗi khi một người hành hương đến viếng thăm ngôi đền thứ , họ sẽ nhận được một lượng "Phúc khí" (may mắn) là . Các ngôi đền được kết nối với nhau bởi con đường mòn một chiều. Con đường thứ bắt đầu từ đền , dẫn đến đền và cần ngày để đi hết quãng đường này. Nghĩa là, nếu xuất phát từ đền vào ngày thứ , người hành hương sẽ đến đền vào ngày thứ .
Một vị thiền sư muốn thực hiện chuyến hành hương kéo dài đúng ngày để tích lũy phúc khí cho bách tính. Kế hoạch cụ thể như sau:
Xuất phát từ Đền Tổ (đền số ) vào ngày thứ .
Kết thúc hành trình và quay trở lại đúng Đền Tổ vào ngày thứ .
Theo quy tắc tu hành khổ hạnh: "Chân không mỏi, tâm không dừng", vị thiền sư không được phép lưu lại qua đêm hay nghỉ ngơi tại bất kỳ ngôi đền nào. Ngay khi đến một ngôi đền và thắp hương (nhận phúc khí), ông phải lập tức lên đường sang ngôi đền tiếp theo trong cùng ngày hôm đó.
Nếu quay lại một ngôi đền nhiều lần, phúc khí vẫn được nhận thêm tương ứng. Phúc khí cũng được tính tại thời điểm xuất phát (ngày 0) và thời điểm kết thúc (ngày ).
Ngoài ra, các vị thần cai quản các ngôi đền sẽ tổ chức buổi "Đại Lễ Cầu May" vào các thời điểm đặc biệt. Cụ thể, Đại Lễ lần thứ diễn ra vào ngày tại ngôi đền . Nếu vị thiền sư có mặt tại đền đúng vào ngày , ngoài lượng phúc khí cơ bản, ông sẽ nhận được thêm lượng phúc khí ban phước từ thần linh.
Là một đệ tử thông tuệ, bạn hãy giúp vị thiền sư tính toán lộ trình sao cho tổng lượng Phúc khí tích lũy được sau chuyến đi là lớn nhất.
Dữ liệu:
Dòng đầu tiên chứa bốn số nguyên , , lần lượt là số lượng ngôi đền, số con đường, tổng thời gian hành hương và số lượng Đại Lễ.
Dòng thứ hai chứa số nguyên , biểu thị lượng phúc khí nhận được tại mỗi ngôi đền.
dòng tiếp theo, mỗi dòng chứa ba số nguyên , mô tả con đường từ đền đến đền mất ngày.
dòng cuối cùng, mỗi dòng chứa ba số nguyên , mô tả Đại Lễ diễn ra vào ngày tại đền với lượng phúc khí thưởng thêm là .
Dữ liệu đảm bảo:
Với mọi , có . Có thể có nhiều con đường một chiều nối cùng một cặp đền.
Từ mỗi ngôi đền luôn có ít nhất một con đường để đi tiếp.
Thời gian tổ chức các Đại Lễ là đôi một khác nhau.
Kết quả:
Một dòng duy nhất chứa một số nguyên là tổng lượng Phúc khí lớn nhất có thể đạt được.
Nếu không thể quay lại Đền Tổ (đền 1) vào đúng ngày thứ , hãy xuất ra -1.
