보물 상자

2014년 정기 고연전 기획을 맡은 기획국장 장홍준은 특별한 행사를 준비하고 있다.

행사는 이렇게 진행된다. 보물 상자가 $N$개 있고, 각 상자의 자물쇠에는 크림슨색 열쇠 구멍과 로얄 블루색 열쇠 구멍이 여러 개씩 달려 있다. 상자를 열면 그 안에 크림슨색 열쇠, 로얄 블루색 열쇠, 무색 열쇠가 들어 있다.

자물쇠에 쓴 열쇠는 소진되어 다시 쓸 수 없다. 크림슨색 열쇠는 크림슨색 열쇠 구멍에만, 로얄 블루색 열쇠는 로얄 블루색 열쇠 구멍에만 쓸 수 있다. 무색 열쇠는 두 종류의 열쇠 구멍에 모두 쓸 수 있다. 상자 하나를 열려면 그 자물쇠의 열쇠 구멍을 전부 채워야 하고, 한 번 연 상자는 다시 열지 않는다.

상품은 열쇠를 가장 많이 모은 사람이 받는다. 상자를 열면 열쇠가 소진되지만 보상으로 다시 열쇠를 받으므로, 어떤 상자를 어떤 순서로 여는지에 따라 손에 남는 열쇠의 개수가 달라진다. 열쇠의 색은 따지지 않고 개수만 센다.

각 상자의 열쇠 구멍 구성과 보상을 알고 있을 때, 모을 수 있는 열쇠의 최대 개수를 구하는 프로그램을 작성하시오.

첫 줄에 보물 상자의 개수 $N$과 처음에 가지고 있는 열쇠의 개수가 주어진다. 열쇠 개수는 크림슨색, 로얄 블루색, 무색 순서다. ($1 \le N \le 12$)

다음 $N$개 줄에 상자의 정보가 한 줄에 하나씩 주어진다. 각 줄에는 정수 다섯 개가 있다. 앞의 두 수는 자물쇠에 있는 크림슨색 열쇠 구멍의 개수 $c_i$와 로얄 블루색 열쇠 구멍의 개수 $r_i$이고, 뒤의 세 수는 그 상자를 열었을 때 얻는 크림슨색, 로얄 블루색, 무색 열쇠의 개수다.

$N$을 제외하고 입력에 주어지는 수는 모두 $0$ 이상 $10$ 이하의 정수다.

모을 수 있는 열쇠의 최대 개수를 출력한다.

예제 입력에서는 먼저 1번 상자를 연다. 크림슨색 열쇠 한 개를 쓰고 무색 열쇠 한 개를 받아, 남은 열쇠는 크림슨색 2개, 로얄 블루색 1개, 무색 3개가 된다. 이어서 남은 여섯 개를 모두 써서 2번 상자를 연다. 크림슨색 열쇠 구멍 두 개는 크림슨색 열쇠로 채우고, 로얄 블루색 열쇠 구멍 네 개는 로얄 블루색 열쇠 한 개와 무색 열쇠 세 개로 채운다. 보상으로 로얄 블루색 열쇠 8개를 받으니 최종 개수는 8이다. 3번 상자는 열쇠 구멍이 12개라 남은 열쇠로는 열 수 없다.