도착일까지 고려한 상품 선택

문제

한 온라인 쇼핑몰은 같은 규격의 물건을 여러 판매자가 등록할 수 있도록 운영한다. 구매자는 그중 정확히 하나를 주문하려고 한다. 각 상품에는 상품 가격, 배송에 걸리는 날짜 수, 사용할 수 있는 쿠폰 금액이 적혀 있다. 상품 번호는 입력되는 순서대로 1번부터 N번까지 붙는다. 서로 다른 상품의 가격과 배송 날짜 수, 쿠폰 금액이 모두 같아도 상품 번호가 다르면 별개의 상품이다. 구매자는 주문한 날로부터 L일 이내에 도착하는 상품만 구매할 수 있다. 배송에 걸리는 날짜 수가 L과 같으면 구매 가능한 상품이며, L보다 크면 가격이 아무리 저렴해도 선택 대상에서 제외한다. 배송에 걸리는 날짜 수가 0인 상품은 주문한 날 도착한다는 뜻이다. 입력에 구매 가능한 상품이 하나도 없을 수도 있다. 각 상품의 결제 금액은 다음과 같이 계산한다. 먼저 상품 가격에서 해당 상품의 쿠폰 금액을 뺀다. 결과가 음수이면 0원으로 바꾼다. 이렇게 구한 금액이 F원 이상이면 배송비는 0원이고, F원 미만이면 배송비 S원을 더한다. 배송비 면제 여부는 반드시 쿠폰을 적용한 뒤의 금액으로 판단한다. 쿠폰은 상품 가격에만 적용하며, 배송비를 깎는 데에는 사용할 수 없다. 상품 하나를 구매할 때 다른 상품의 쿠폰을 가져와 쓸 수도 없다. 구매 가능한 상품 중 결제 금액이 가장 작은 상품을 선택한다. 결제 금액이 같은 상품이 여러 개이면 배송에 걸리는 날짜 수가 가장 작은 상품을 선택한다. 날짜 수도 같으면 상품 번호가 가장 작은 상품을 선택한다. 이 규칙에 따라 선택되는 상품은 구매 가능한 상품이 있을 때 항상 하나로 정해진다. 상품을 여러 개 묶어서 주문하거나 배송비를 나누어 내는 경우는 고려하지 않는다. 선택할 상품 번호와 그 상품의 결제 금액을 구하는 프로그램을 작성한다.

입력

첫째 줄에 상품 수 N, 허용 배송 날짜 수 L, 무료 배송 기준 금액 F, 일반 배송비 S가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 20,000, 0 ≤ L ≤ 30, 1 ≤ F ≤ 1,000, 0 ≤ S ≤ 1,000이다.
다음 N개 줄에는 상품 가격 P, 배송에 걸리는 날짜 수 D, 쿠폰 금액 C가 공백으로 구분되어 주어진다. 0 ≤ P ≤ 1,000, 0 ≤ D ≤ 30, 0 ≤ C ≤ 1,000이다. 입력의 모든 수는 정수이며, 금액의 단위는 원이다.

출력

구매 가능한 상품이 있으면 선택한 상품 번호와 결제 금액을 공백으로 구분하여 한 줄에 출력한다. 구매 가능한 상품이 없으면 -1만 출력한다.

4 3 500 100
550 2 100
500 3 0
600 1 100
500 1 0

3 500

2 0 300 40
0 1 100
700 2 0

-1

3 2 100 30
20 2 50
0 1 0
10 1 20

2 30

출처: Devin.KR 자체 제작