Đàn bò của nông dân John đang luyện tập cho một cuộc chạy vượt rào sắp diễn ra. Nông trại của John có cánh đồng và con đường , mỗi con đường được kí hiệu bởi hai chỉ số và mô tả một đường đi một chiều từ đến . Ngoài ra, trên mỗi con đường, nông dân John đặt chướng ngại vật độ cao .
Lũ bò sẽ tập chạy trong vòng , mỗi vòng chúng sẽ chạy từ đồng cỏ đến . Do chúng rất lười biếng nên chúng sẽ chọn con đường mà độ cao của chướng ngại vật cao nhất cần phải vượt qua là thấp nhất. Nói cách khác, nếu gọi là kết quả
của lượt chạy này, không có chướng ngại vật nào trên đường chạy này có độ cao lớn hơn .
Hãy giúp lũ bò chọn ra đường chạy tối ưu.
Dữ liệu vào:
Dòng đầu tiên chứa ba số nguyên và ;
dòng tiếp theo, mỗi dòng chứa ba số nguyên mô tả một con đường tương ứng;
dòng tiếp theo, mỗi dòng chứa hai số nguyên và .
Dữ liệu ra:
Đưa ra dòng là độ cao của đường chạy tối ưu trong vòng chạy tương ứng, hoặc trong trường hợp không có đường đi từ đến .
