레벨 업

MMORPG의 팬인 Steve는 World of Warcraft Classic이 발표되었을 때 매우 기뻐했다. 그는 첫날부터 게임을 시작했고, 지금은 최고 레벨까지 두 레벨만 남았다. 게임이 처음 나왔을 때만큼 시간이 많지 않아서, 이 두 레벨을 최대한 빨리 끝내고 싶어 한다.

첫 번째 레벨을 통과하려면 Steve는 $s_1$만큼의 경험치가 필요하다. 그 경험치를 얻어야만 두 번째 레벨로 올라갈 수 있고, 두 번째 레벨을 통과하려면 $s_2$만큼의 경험치를 더 얻어야 한다.

Steve에게는 $n$개의 퀘스트 목록이 있다. 이 퀘스트들로 두 레벨을 모두 끝낼 수 있다는 것을 그는 안다. $i$번째 퀘스트를 통과하는 데 $t_i$분이 걸린다. 그 대가로 이 퀘스트에서 $x_i$의 경험치를 얻는다.

다음 레벨로 올려 주는 퀘스트를 완료하면, 넘친 경험치만큼 다음 레벨에 필요한 경험치가 줄어든다. 레벨이 오른 뒤 남은 퀘스트들은 $y_i$의 경험치를 주지만, 필요한 시간도 $r_i$로 줄어든다.

퀘스트를 완료하면 다른 레벨에서도 그 퀘스트를 다시 수행할 수 없다.

퀘스트 목록이 주어졌을 때, Steve가 마지막 두 레벨을 가장 빨리 끝내도록 퀘스트를 수행하는 순서를 정하라.

첫 줄에 세 정수 $n$, $s_1$, $s_2$ ($1 \le n, s_1, s_2 \le 500$)가 주어진다. 각각 퀘스트의 개수, 첫 번째 레벨에 필요한 경험치, 두 번째 레벨에 필요한 경험치이다.

이어지는 $n$개의 줄에는 네 정수 $x_i$, $t_i$, $y_i$, $r_i$ ($1 \le y_i < x_i \le 500$, $1 \le r_i < t_i \le 10^9$)가 주어진다. $x_i$와 $y_i$는 $i$번째 퀘스트를 첫 번째 레벨과 두 번째 레벨에서 수행했을 때 얻는 경험치이고, $t_i$와 $r_i$는 같은 순서로 그 퀘스트를 통과하는 데 필요한 분이다.

Steve가 두 레벨을 모두 끝내는 데 필요한 최소 시간(분)을 한 개의 수로 출력한다. 두 레벨을 모두 끝낼 방법이 없으면 $-1$을 출력한다.