Giáo sư Y rất hào phóng, ông có học trò và ông đã chuẩn bị bữa tiệc mừng cho các học trò của mình. Trong các bữa tiệc ông sử dụng Cocktail để thiết đãi các học trò, ông cũng biết được lượng Cocktail tối thiểu của mỗi học trò mà khi họ uống đủ lượng bằng đấy thì sẽ thấy sảng khoái.
Các học trò của giáo sư đều là những Contestant rất giỏi và luôn có những Solution độc đáo trong các kỳ thi CSLPreVNOI. Trong số các học trò của giáo sư có cặp là bạn bè (một người có thể là bạn bè với nhiều người). Với mỗi cặp bạn bè, nếu trong bữa tiệc cả hai cùng thấy sảng khoái, họ sẽ trao đổi Solution của mình với nhau. Khi một người A trao đổi Solution của mình với người B, người B có thể đem Solution đó trao đổi với người khác (tất nhiên, theo phép lịch sự, B sẽ không trao đổi ngay Solution đó với A, nhưng có thể B trao đổi với C rồi C lại trao đổi lại với A), nhưng thật may là các mối quan hệ bạn bè trong các học trò của giáo sư được hình thành theo cách mà Solution của người A sẽ không thể trao đổi lại với người A trong bữa tiệc, bất kể thứ tự xảy ra các trao đổi như thế nào.
Giáo sư đã chuẩn bị những lượng Cocktail nhất định cho các bữa tiệc của mình. Trong mỗi bữa tiệc, giáo sư muốn có nhiều học trò trao đổi Solution, vì vậy ông muốn chia lượng Cocktail cho các học trò của mình sao cho số lượng người trao đổi Solution là nhiều nhất có thể.
Bạn, một học trò xuất sắc của giáo sư, hãy giúp giáo sư tính toán điều đó.
Dữ liệu vào:
Dòng đầu chứa hai số nguyên dương là số học trò của giáo sư tham gia các bữa tiệc và số cặp là bạn bè.
Dòng thứ hai chứa số nguyên dương , trong đó số là lượng Cocktail tối thiểu để người thứ đạt sảng khoái.
Dòng thứ trong số dòng tiếp theo chứa hai số nguyên dương cho biết và là bạn bè.
Dòng tiếp theo chứa một số nguyên dương là số bữa tiệc mà giáo sư sẽ tổ chức.
dòng tiếp theo, dòng thứ chứa số nguyên là số lượng Cocktail giáo sư chuẩn bị để phục vụ trong bữa tiệc thứ .
Dữ liệu ra:
Ghi ra dòng, dòng thứ là số lượng lớn nhất người trao đổi Solution với bạn bè trong bữa tiệc thứ . Lưu ý rằng các bữa tiệc là độc lập.
Giới hạn:
Subtask : số test tương ứng với số điểm có và mỗi người có quan hệ bạn bè với không quá hai người khác;
Subtask : số test khác tương ứng với số điểm có
và mỗi người có quan hệ bạn bè với không quá hai người khác;
Subtask : số test khác tương ứng với số điểm có ;
Subtask : số test còn lại tương ứng với số điểm không có ràng buộc gì thêm.
Ví dụ (Tải test đề bài và 2 test mẫu khác ở "Tệp đính kèm" phía trên đề bài):
