20925번 - 메이플스토리

상원이는 겨울방학 동안 메이플스토리를 할 것이다. 개강 후에는 바쁘기 때문에 방학 동안 최대한 레벨을 많이 올리려고 한다.

메이플스토리에는 여러 가지 사냥터가 있다. 각 사냥터는 입장에 필요한 최소 레벨, 지형, 몬스터 레벨, 몬스터 수, 버닝 등등 다양한 특징을 가진다. 상원이는 경험치가 가장 중요하기 때문에 사냥터의 특징을 입장에 필요한 최소 경험치와 $1$분마다 얻는 경험치로 간략화했다. 사냥을 시작하고 매 분마다 지금 있는 사냥터에서 계속 사냥할지 다른 사냥터로 갈지 결정한다. 코디 아이템에 돈을 다 써 텔레포트를 할 수 없는 상원이는 사냥터 사이를 직접 걸어서 이동한다. 사냥터 사이를 이동하는 동안 사냥을 할 수 없기 때문에 경험치를 얻을 수 없다.

처음에 캐릭터의 경험치는 $0$이기 때문에 입장에 필요한 최소 경험치가 $0$인 사냥터 중 하나를 골라 사냥을 시작한다. 상원이가 방학 동안 얻을 수 있는 경험치의 최댓값을 알려주자.

첫째 줄 사냥터 수 $N$ ($1 \le N \le 200$)과 방학 기간을 분 단위로 나타낸 $T$ ($1 \le T \le 1\,000$)가 주어진다.

다음 $N$개의 줄에는 $i$번째 사냥터의 특징인 입장에 필요한 최소 경험치 $c_i$와 $1$분마다 얻는 경험치 $e_i$가 주어진다. ($0 \le c_i, e_i \le 1\,000\,000$)

다음 $N$개의 줄에는 각 사냥터 사이를 이동하는 데 걸리는 시간이 주어진다. $i$번째 줄의 $j$번째 수는 $i$번 사냥터에서 $j$번 사냥터로 이동하여 입장하는 데까지 걸리는 시간을 분 단위로 나타낸 값 $t_{i,j}$이다. ($1 \le t_{i,j} \le 1\,000$, $t_{i,j}=t_{j,i}$, $t_{i,i}=0$)

단, 입장에 필요한 최소 경험치 $c_i$가 $0$인 사냥터는 반드시 하나 이상 존재한다.

상원이가 방학 동안 얻을 수 있는 경험치의 최댓값을 출력한다.