친구가 없다면 친구를 사자 (Bribing Friends)

영기는 이번에 새로 나온 영화 "The Jungol"을 보고싶다. 그러나 영기는 친구가 없어서 돈을 주고 친구를 사서 영화를 같이 보러 가고자한다.

영기에게는 커피 기프티콘과 카페 쿠폰(한 장에 도장이 한 개씩 찍혀있다)이 있다.

영기에게는 N명의 지인이 있는데, i번째 지인은 P_i의 인기도를 가지고 있다.

인기를 갈망하는 영기는 영화관을 함께가는 친구들의 총 인기도의 합을 최대로 만들고 싶다.

그러나 i번째 친구는 C_i개의 기프티콘을 줘야지만 함께 영화관을 가준다.

다행히 X_i 개의 쿠폰을 주면 한 개의 기프티콘의 개수를 깎아준다. (너무 착하다!)

물론 쿠폰만 충분하다면 기프티콘을 하나도 안줘도 된다.

영기에게 A개의 기프티콘과 B개의 쿠폰이 있다면, 영기가 영화관에 함께가는 친구들의 총 인기도의 합의 최댓값이 얼마인지 출력하시오.

입력

첫 번째 줄에 친구 수 N, 기프티콘의 수 A, 쿠폰의 수 B가 입력된다 (1≤N≤2\,000, 0≤A, B≤2\,000).

두 번째 줄부터 N줄에 걸쳐 i번째 친구의 인기도 P_i, 요구하는 기프티콘 수 C_i, 기프티콘 한 개를 할인해주는데 필요한 쿠폰 수 X_i가 입력된다 (1≤P_i, C_i, X_i≤2\,000).

출력

영기가 영화관에 함께가는 친구들의 총 인기도의 합의 최댓값이 얼마인지 출력하시오.

예제1

힌트

출처

USACO 2022 December Gold

친구가 없다면 친구를 사자 (Bribing Friends) 1초 256MB