Treasure Chests

Jang Hongjun, the planning director for the 2014 Korea University and Yonsei University annual games, is preparing a special event.

The event works like this. There are $N$ treasure chests, and the lock on each chest has several crimson keyholes and several royal blue keyholes. Inside a chest are crimson keys, royal blue keys and colorless keys.

A key used on a lock is spent and cannot be used again. A crimson key fits crimson keyholes only, and a royal blue key fits royal blue keyholes only. A colorless key fits both kinds of keyhole. Opening a chest means filling every keyhole on its lock, and a chest that has been opened is never opened again.

The prize goes to whoever collects the most keys. Opening a chest spends keys but pays keys back, so the number left in your hand depends on which chests you open and in what order. The color of a key does not matter, only the count.

Given the keyholes on every lock and the reward inside every chest, write a program that finds the largest number of keys you can collect.

The first line contains the number of treasure chests $N$ and the number of keys you start with, in the order crimson, royal blue, colorless. ($1 \le N \le 12$)

Each of the next $N$ lines describes one chest with five integers. The first two are the number of crimson keyholes $c_i$ and the number of royal blue keyholes $r_i$ on the lock. The last three are the number of crimson, royal blue and colorless keys you receive when that chest is opened.

Every number in the input other than $N$ is an integer between $0$ and $10$.

Print the largest number of keys you can collect.

In the sample input, chest 1 is opened first. One crimson key is spent and one colorless key comes back, leaving 2 crimson, 1 royal blue and 3 colorless keys. All six of those go into chest 2: the two crimson keyholes take two crimson keys, and the four royal blue keyholes take one royal blue key and three colorless keys. The reward is 8 royal blue keys, so the final count is 8. Chest 3 has 12 keyholes and cannot be opened with what is left.