25216번 - 파밍 루트

경태는 인하대학교에서 유행하는 게임 Conquer The Planet(이하 CTP)에 빠져있다. CTP를 열심히 플레이하던 어느 날, 경태는 게임 속에 숨겨져 있던 던전을 발견했다! 던전 입구에는 플레이어를 위한 설명서가 붙어있었다.

설명서의 내용은 다음과 같다.

• 던전은 한 번만 입장할 수 있다.
• 던전에는 \(N\)개의 구역과 \(M\)개의 포탈이 존재한다. 각 구역은 1번부터 \(N\)번까지 번호가 매겨져 있다. 던전에 입장하면 1번 구역에서 시작한다. 포탈은 출발 구역과 도착 구역의 쌍으로 구성된다. 출발 구역에 위치한 포탈을 통해 도착 구역으로 순간이동할 수 있다. 단, 어떤 구역에도 도착 구역이 같은 서로 다른 두 포탈은 존재하지 않는다. 순간이동 시 소요되는 시간은 없다.
• 던전에 머무를 수 있는 제한 시간 \(T\)분이 지나면 던전에서 퇴장당한다.
• 각 구역에는 몬스터가 한 마리씩 존재한다. 몬스터는 플레이어가 포탈을 사용하는 것을 방해한다. 플레이어가 어떤 구역에 있는 포탈을 사용하려면 먼저 전투를 통해 해당 구역의 몬스터를 쓰러트려야 한다.
• 전투는 몬스터와 플레이어가 번갈아가면서 공격하는 것으로 이뤄진다. 선공은 항상 몬스터이다. 한쪽의 체력이 0 이하가 되어 쓰러지면 전투가 종료된다. 모든 전투는 시작부터 종료까지 항상 1분이 소요된다.
• 몬스터의 기본 공격력을 \(a\), 시간당 공격력 증가량을 \(x\), 플레이어 방어력당 공격력 감소량을 \(y\)라고 하자. 던전 입장 후 \(t\)분이 지난 시점에 시작한 전투에서, 방어력이 \(d\)인 플레이어가 몬스터의 공격을 받으면 체력이 \(max(0, a+xt-yd)\)만큼 감소한다. 단, 플레이어의 방어력은 항상 양의 정수이다.
• 전투에서 플레이어가 몬스터를 쓰러트릴 경우, 플레이어는 몬스터가 떨어트리는 금화를 획득한다. 몬스터를 쓰러트림과 동시에 던전의 제한 시간이 끝나도 금화를 획득할 수 있다. 몬스터는 플레이어가 구역을 떠난 직후 제자리에서 부활한다.
• 전투에서 플레이어가 쓰러질 경우, 플레이어는 던전에서 퇴장당한다.

경태는 강한 것이 좋기 때문에 공격력에 올인하기로 했다. 따라서 어떤 몬스터든 일격에 쓰러트릴 수 있다. 그러나 이에 대한 대가로 경태의 체력은 단 1에 불과하다. 던전에서 최대한 많은 금화를 모으기 위해 경태에게 필요한 방어력의 최솟값을 구해보자.

첫째 줄에 구역의 개수 \(N\), 포탈의 개수 \(M\), 제한 시간 \(T\)가 주어진다.

이어서 \(N\)개의 줄에 걸쳐 \(i\)번 구역에 있는 몬스터의 정보 \(a_i\), \(x_i\), \(y_i\), \(c_i\)가 주어진다. 각각 몬스터의 기본 공격력, 시간당 공격력 증가량, 플레이어 방어력당 공격력 감소량, 떨어트리는 금화의 개수를 의미한다.

이어서 \(M\)개의 줄에 걸쳐 포탈의 출발 구역 \(u\)와 도착 구역 \(v\)가 주어진다. 이는 \(u\)번 구역에 위치한 포탈을 통해 \(v\)번 구역으로 순간이동할 수 있음을 의미한다. (단, \(u\) ≠ \(v\))

첫째 줄에 문제의 답을 출력한다.

• 2 ≤ \(N\) ≤ 5,000
• 1 ≤ \(M\) ≤ 50,000
• 1 ≤ \(T\) ≤ 100
• 1 ≤ \(a_i\) ≤ 10⁹
• 1 ≤ \(x_i\), \(y_i\), \(c_i\) ≤ 10,000
• 1 ≤ \(u\), \(v\) ≤ \(N\), \(u\) ≠ \(v\)
• 입력으로 주어지는 모든 수는 양의 정수이다.