비타민

겨울에는 비타민을 충분히 섭취하는 것이 중요하다. 아다마스도 이를 알고 있어서 여러 종류의 종합비타민 정제를 파는 약국 Vitaminų Pasaulis에 들어갔다. 비타민을 지나치게 먹으면 몸에 해로울 수 있으므로, 이 약국은 한 손님에게 같은 종류의 정제를 한 개씩만 판매한다.

아다마스가 가장 관심을 가지는 것은 면역력을 높이는 비타민 C와 뼈와 치아에 꼭 필요한 비타민 D이다. 그런데 가게에 정제 종류가 너무 많아서 아다마스는 어떤 것을 골라야 할지 헷갈린다.

각 정제에 들어 있는 비타민 C와 비타민 D의 양, 그리고 정제의 가격이 주어진다. 아다마스가 비타민 C를 최소 $C$밀리그램, 비타민 D를 최소 $D$밀리그램 얻으려면 최소 얼마를 지불해야 하는지 구하라.

첫 줄에는 세 정수가 주어진다. 정제의 개수 $N$, 그리고 아다마스가 원하는 비타민 양 $C$와 $D$이다.

다음 $N$개의 줄에는 정제가 하나씩 주어진다. 각 줄에는 비타민 C의 양 $c_i$, 비타민 D의 양 $d_i$(밀리그램 단위), 정제의 가격 $k_i$(센트 단위)가 차례로 적혀 있다. 모든 수는 정수이다.

비타민 C를 최소 $C$밀리그램, 비타민 D를 최소 $D$밀리그램 얻기 위해 아다마스가 지불해야 하는 최소 센트 수를 정수 하나로 출력하라.

모든 정제를 사면 아다마스는 필요한 양 이상을 얻으므로, 해는 항상 존재한다.

• $1 \le N \le 100$
• $0 \le c_i, C \le 10\,000$
• $0 \le d_i, D \le 500$
• $1 \le k_i \le 1000$