lntanx는 농장에 요소 비료를 납품하는 일을 하고 있다. 어느 날 한 농장에서 요소 비료 주문이 들어왔다. 이번 주문에 필요한 비료를 만들려면 암모니아가 통 필요하다. 창고에 암모니아가 남아 있지 않아, lntanx는 질소와 수소를 구매해 암모니아를 직접 합성하기로 했다.
합성을 한 번 할 때마다 질소 통과 수소 통을 사용해 암모니아 통을 얻는다. 합성은 정수 횟수만큼 할 수 있고, 필요한 양보다 많이 생산해도 된다. 합성 자체에는 비용이 들지 않는다.
각 거래처는 질소와 수소 중 한 종류만 판매한다. lntanx는 각 거래처에서 판매 가능 수량을 넘지 않는 범위에서 원하는 정수 수량만큼 구매할 수 있다. 한 번의 합성에 필요한 원료를 여러 거래처에서 나누어 사도 된다.
암모니아를 통 이상 합성하는 데 필요한 최소 구매 비용을 구하자.
첫째 줄에 질소 거래처의 수 , 수소 거래처의 수 , 필요한 암모니아의 양 가 공백으로 구분되어 주어진다.
다음 개의 줄에는 질소 거래처의 정보가 한 줄에 하나씩 주어진다. 이어지는 개의 줄에는 수소 거래처의 정보가 한 줄에 하나씩 주어진다. 각 거래처의 정보는 재고량 와 통당 가격 가 공백으로 구분되어 주어진다.
첫째 줄에 최소 비용을 출력한다. 원료가 부족해 암모니아를 통 이상 만들 수 없다면 -1을 출력한다.
비용을 계산할 때 부호 있는 64비트 정수 자료형을 사용하는 것을 권장한다.
암모니아를 통 이상 얻으려면 최소 번 합성해야 한다. 따라서 질소 통과 수소 통이 필요하다.
질소는 통당 가격이 인 거래처에서 통, 인 거래처에서 통을 사면 이 든다. 수소는 통당 가격이 인 거래처에서 통, 인 거래처에서 통을 사면 이 든다. 따라서 최소 구매 비용은 이다.