9499번 - 보물 상자

2014년 정기 고연전 기획을 맡은 기획국장 장홍준은 특별한 행사를 계획 중이다.

행사의 내용은 이렇다. N개의 보물 상자가 있고 각 보물 상자의 자물쇠에는 크림슨색 열쇠 구멍 여러 개와 로얄 블루색 열쇠 구멍 여러 개가 있다. 보물 상자를 열면 크림슨색 열쇠 여러 개와 로얄 블루색 열쇠 여러 개, 무색 열쇠 여러 개가 안에 들어있다.

보물 상자를 열기 위해 열쇠를 사용하면 소진되어 다음에 다시 사용할 수 없다. 크림슨색 열쇠는 크림슨색 열쇠 구멍에만 사용할 수 있고, 로얄 블루색 열쇠는 로얄 블루색 열쇠 구멍에만 사용할 수 있다. 무색 열쇠는 두 종류의 열쇠 구멍 모두 사용할 수 있다.

행사의 상품을 받기 위해서는 열쇠를 가장 많이 모아야한다. 보물 상자를 열면 일부 열쇠는 소진되어 없어지지만, 보상으로 열쇠를 더 받을 수 있다. 열쇠의 색은 중요하지 않고, 오직 개수만 많으면 상품을 받을 수 있다.

각 보물 상자의 자물쇠에 어떤 열쇠 구멍들이 있는지와 각 보물 상자의 보상을 알고 있을 때, 얻을 수 있는 열쇠의 최대 개수를 구하자.

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

다음 N개의 줄에 각 보물 상자에 대한 정보가 주어진다.

처음에 주어지는 수는 자물쇠에 있는 크림슨색 열쇠 구멍의 개수 c[i]이다.

다음에 주어지는 수는 자물쇠에 있는 로얄 블루색 열쇠 구멍의 개수 r[i]이다.

다음에 주어지는 세 수는 순서대로 보물 상자를 열었을 때 얻는 크림슨색, 로얄 블루색, 무색 열쇠의 개수가 주어진다.

입력으로 주어지는 수는 음이 아닌 정수이며 10보다 크지 않다.

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

처음에 1번 보물 상자를 연다. 이후 가지고 있는 열쇠의 개수는 크림슨색 열쇠 2개, 로얄 블루색 열쇠 1개, 무색 열쇠 3개가 된다. 그리고 모든 열쇠를 사용하여 2번 보물 상자를 연다. 이후 가지고 있는 열쇠의 개수는 로얄 블루색 열쇠 8개다.