서울에서 경산까지

배우 한정올 씨는 이번 여름에 서울에서 경산까지 이동하면서 모금 활동을 하기로 했다. 거쳐 갈 도시와 방문 순서는 미리 정해져 있고, 여행은 서울에서 출발해 각 도시를 정해진 순서대로 한 번씩 들른 뒤 경산에서 끝난다.

서울을 제외한 도시의 개수를 $N$이라고 하자. 서울에서 두 번째 도시까지 가는 구간이 구간 1, 두 번째 도시에서 세 번째 도시까지 가는 구간이 구간 2이고, 마지막으로 경산에 도착하는 구간이 구간 $N$이다. 구간은 모두 $N$개다. 각 구간은 도보와 자전거 중 하나를 골라 이동한다. 구간마다 도보로 이동할 때 걸리는 시간(분)과 그때 얻는 모금액(원), 자전거로 이동할 때 걸리는 시간(분)과 그때 얻는 모금액(원)이 정해져 있다.

서울과 경산 사이에 도시가 두 개 있는 경우($N = 3$)를 예로 들어 보자.

구간마다 도보와 자전거 중 무엇을 고르느냐에 따라 전체 모금액과 전체 이동 시간이 달라진다. 시간이 넉넉하다면 모든 구간을 도보로 이동하는 것이 모금액을 최대로 하는 방법이고, 모금액은 200 + 370 + 250 = 820원, 걸리는 시간은 500 + 800 + 700 = 2000분이다.

그러나 한정올 씨가 자선 여행에 쓸 수 있는 시간은 $K$분으로 한정되어 있다. 위 예에서 $K = 1650$이라면 구간 1과 구간 2는 도보로, 구간 3은 자전거로 이동해 모금액 660원을 얻는 것이 가장 좋고, 이때 걸리는 시간은 1600분이다.

구간별로 도보와 자전거의 시간과 모금액이 주어질 때, $K$분 이내에 서울에서 경산까지 이동하면서 모을 수 있는 최대 모금액을 구하는 프로그램을 작성하시오. $K$분 이내에 여행하는 방법은 항상 존재한다.

첫째 줄에 두 자연수 $N$과 $K$가 공백으로 구분되어 주어진다($3 \le N \le 100$, $0 < K \le 100000$).

둘째 줄부터 $N + 1$번째 줄까지 각 줄에 네 자연수가 공백으로 구분되어 주어진다. $i + 1$번째 줄은 구간 $i$의 정보이고, 차례로 도보로 이동할 때 걸리는 시간(분), 그때 얻는 모금액(원), 자전거로 이동할 때 걸리는 시간(분), 그때 얻는 모금액(원)을 뜻한다. 시간을 나타내는 값은 10000 이하이고, 모금액을 나타내는 값은 1000000 이하다. 입력은 모두 $N + 1$줄이다.

$K$분 이내에 여행하면서 모을 수 있는 최대 모금액을 첫째 줄에 출력한다.