배우 한정올 씨는 이번 여름에 서울에서 경산까지 자선 여행을 하면서 모금활동을 진행할 계획이다. 

자선 여행에서 거쳐 가게 될 도시의 개수와 순서는 미리 정해져 있으며, 

자선 여행은 서울에서 시작하여 각 도시를 정해진 순서대로 단 한 번씩 방문한 후 경산에서 끝난다. 

 

서울을 제외한 도시의 개수를 N이라 하자. 이 때 서울에서 두 번째 도시까지 가는 구간을 구간 1, 

두 번째 도시부터 세 번째 도시까지 가는 구간을 구간 2와 같이 부르기로 하며, 

마지막 목적지인 경산에 도착하는 구간을 구간 N이라 하자.

즉, 구간의 전체 개수는 N이다. 

 

구간 사이의 이동은 도보 혹은 자전거 어느 한 쪽을 이용하게 되는데, 

각 구간에는 도보로 이동할 때 걸리는 시간(분), 이 때 얻게 되는 모금액(원), 

자전거로 이동할 때 걸리는 시간(분), 이 때 얻게 되는 모금액(원)이 정해져 있다.

 

예를 들어, 서울과 경산 사이에 2개의 도시가 있는 다음과 같은 경우(N = 3)를 생각해 보자.

 

인접한 도시 사이를 도보로 이동하는지 자전거로 이동하는지에 따라 전체 모금액이나 걸리는 시간에 차이가 생기게 된다. 

한정올 씨는 전체 모금액을 가능한 많이 얻는 방법을 찾고 싶어 한다. 

위의 예에서는 시간이 충분하다면 모든 구간을 도보로 이동하는 것이 모금액을 최대로 하는 방법이며, 

모금액은 200+370+250 = 820원, 여행에 걸리는 시간은 500+800+700 = 2,000분이다.

 

그러나 한정올 씨는 바쁜 스케줄로 인해 자선 여행을 위해 보낼 수 있는 시간이 K분(K는 자연수)으로 한정되어 있다. 

위의 예에서 만약 K=1,650이라면, 

1, 2번 구간은 도보로 이동하고 3번 구간은 자전거로 이동하여 모금액을 660원으로 하는 것이 가장 좋은 방법이며, 

이 때 걸리는 시간은 1,600분이다.

 

위와 같이 각 구간별로 도보 및 자전거로 이동하는 경우 걸리는 시간과 모금액이 주어질 때,

제한시간 이내로 서울에서 경산까지 여행하면서 모금할 수 있는 최대 금액을 찾는 프로그램을 작성하시오.

(제한시간 이내에 여행하는 방법은 항상 존재한다.)
 

표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 두 자연수 N과 K가 공백으로 분리되어 주어진다(3 ≤ N ≤ 100, 0 < k ≤ 100,000). 두 번째 줄에는 구간 1을 도보로 이동할 때 걸리는 시간(분), 이 때 얻게 되는 모금액(원), 자전거로 이동할 때 걸리는 시간(분), 이 때 얻게 되는 모금액(원)을 나타내는 네 개의 자연수가 차례로 공백으로 분리되어 주어진다. 세 번째 줄부터 N+1번 째 줄도 마찬가지 형식으로 각 줄마다 네 개의 자연수가 주어지며, 입력은 총 N+1줄로 구성된다. 두 번째 줄부터 N+1번 째 줄에 주어지는 숫자들 중 시간을 나타내는 숫자(각 줄의 첫 번째, 세 번째 숫자)는 10,000 이하의 자연수, 모금액을 나타내는 숫자(각 줄의 두 번째, 네 번째 숫자)는 1,000,000 이하의 자연수들이다.

표준 출력으로 K분 이내로 여행하면서 모금할 수 있는 최대 금액을 출력한다. (K분 이내에 여행하는 방법은 항상 존재한다.) 부분문제의 제약 조건 ● 부분문제 1: 전체 점수 100점 중 29점에 해당하며 N의 범위를 N ≤ 20으로 제한한다. ● 부분문제 2: 전체 점수 100점 중 71점에 해당하며 원래의 제약조건 이외에 아무 제약조건이 없다.

3 1650
500 200 200 100
800 370 300 120
700 250 300 90

660

4 3000
1000 2000 300 700
1100 1900 400 900
900 1800 400 700
1200 2300 500 1200

5900

3 600
500 150 200 1000
100 835 200 324
200 125 300 900

2735