여행을 하면 항상 비용이 발생된다.

창환이는 아프리카의 어떤 지역을 여행하다가 몇 개의 지점에서 매우 값이 나가는 광석들이 있는 것을 발견하였다.

그 지역은 N(1≤N≤500)개의 지점으로 이루어져 있으며, 각 지점마다 1부터 N까지의 번호가 붙어 있다.

이들 사이를 잇는 M(1≤M≤2500)개의 길이 있으며, W(1≤W≤200)개의 길에는 값이 나가는 광석이 무한정 놓여 있지만

그 길을 지날 때마다 가지고 올 수 있는 광석의 양은 한정되어 있다.

창환이는 이 지역에서 여행을 하면서 돈을 벌 수 있을지 곰곰이 생각을 해 보았다.

어떤 지점에서 출발하여 다시 그 지점까지 돌아오려면 비용이 발생하는데

그 발생한 비용보다 더 많은 가치의 광석을 가지고 올 수 있다면 돈을 벌 수 있는 것이다.

고민에 빠진 창환이를 도와 돈을 버는 것이 가능한지 판단하는 프로그램을 작성해 주자.

돈버는 여행 timer 1s memory 64MB

돈버는 여행 1s 64MB