ALERT - Báo động đỏ

Giới hạn
  • Thời gian: 0.1s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua Codeforces (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên Codeforces. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên Codeforces

Thế giới những năm 2077 hình thành nên 2 thái cực rõ ràng , các nước hoặc là đi theo con đường Chủ Nghĩa Xã Hội hoặc là theo Tư Bản Chủ Nghĩa. Khởi xướng nên các luồng tư tưởng này là 2 nước Lào và Campuchia . Lào và 1 số nước thân Lào theo đường lối Xã Hội Chủ Nghĩa còn Campuchia và 1 số nước thân Campuchia theo Tư Bản Chủ Nghĩa. Như ta đã biết nền kinh tế các năm trong tương lai là nền kinh tế tri thức và của các mối quan hệ. Nếu trước đây 2 nước X và Y có quan hệ kinh tế là Z tỉ đôla với nhau và giờ X theo CNXH còn Y theo TBCN thì 2 nước này sẽ cắt đứt mối quan hệ kinh tế với nhau , đối với nền kinh tế thế giới thì thực sự là 1 tổn thất lớn , còn nếu 2 nước cùng đi theo cùng 1 con đường chính trị thì mối quan hệ đó vẫn được duy trì . Tuy nhiên năm nay mới là năm 2007 vì thế mới chỉ có Lào , các nước thân Lào là theo CNXH và Campuchia và các nước thân Campuchia theo TBCN , còn lại các nước vẫn theo con đường trung lập và tới năm 2077 họ mới chọn TBCN hay là XHCN.
Biết bạn rất giỏi lập trình , các chuyên gia thuộc Liên Hợp Quốc muốn nhờ bạn hãy lập trình tính xem tới năm 2077 thì trong tình huống tốt nhất thì Tổng Giá Trị Kinh Tế Toàn Cầu là bao nhiêu ? Biết rằng Tổng Giá Trị Kinh Tế Toàn Cầu được tính bằng tổng giá trị các mối quan hệ kinh tế giữa các nước trên thế giới .

Input

Dòng 1 : Số nguyên dương N ( 1 ≤ N ≤ 200 ) là số lượng các quốc gia trên thế giới , các quốc gia được đánh số thứ tự từ 1 -> N .
Dòng 2 : Số nguyên dương L là các nước tính tới thời điểm hiện tại đang theo CNXH .
Dòng 3 : Gồm L số nguyên dương là chỉ số của các nước đang theo CNXH .
Dòng 4 : Số nguyên dương C là các nước tính tới thời điểm hiện tại đang theo TBCN.
Dòng 5 : Gồm C số nguyên dương là chỉ số của các nước đang theo TBCN .
Dòng 6 : Số nguyên dương M ( 1 ≤ M ≤ N*(N-1)/2 ) là số quan hệ kinh tế giữa các nước trên thế giới .
M dòng tiếp theo , dòng thứ i gồm 3 số nguyên dương Xi Yi Zi ( 1 ≤ Xi ≠ Yi ≤ N , 1 ≤ Zi ≤ 1000 ) mô tả 1 mối quan hệ kinh tế .

Output

Dòng 1 : Số nguyên dương K là Tổng Giá Trị Kinh Tế Toàn Cầu trong tình huống tốt nhất và số nguyên dương T là số nước theo XHCN trong tình huống đó .
Dòng 2 : Ghi ra chỉ số của T nước theo CNXH trong tình huống tốt nhất đó. Nếu có nhiều phương án thì chỉ ra phương án mà có số lượng nước theo CNXH là nhiều nhất .

Example

Input:
3
1
1
1
3
1
1 2 10

Output:
10 2
1 2


  • Người up: hard7771988