한 끼와 쿠폰 고르기

문제

한 배달 앱에는 지금 주문할 수 있는 식당 N곳이 표시되어 있다. 사용자는 이 중 정확히 한 식당에서 정해진 한 끼 메뉴를 주문하려 한다. 각 식당에는 메뉴 가격과 배달비가 정해져 있으며, 추가 메뉴나 수량 변경은 고려하지 않는다. 식당 번호는 입력에 주어지는 순서대로 1번부터 N번까지다. 사용자가 가진 쿠폰은 K장이다. 각 쿠폰에는 최소 메뉴 금액과 할인 금액이 적혀 있다. 쿠폰 번호도 입력 순서대로 1번부터 K번까지다. 쿠폰은 어느 식당에서나 사용할 수 있지만, 선택한 식당의 원래 메뉴 가격이 그 쿠폰의 최소 메뉴 금액 이상이어야 한다. 배달비는 쿠폰 사용 조건을 판단할 때 더하지 않는다. 메뉴 가격이 최소 메뉴 금액과 같을 때에도 쿠폰을 사용할 수 있다. 한 주문에는 쿠폰을 최대 한 장만 사용할 수 있으며, 쿠폰을 사용하지 않아도 된다. 쿠폰을 사용하면 메뉴 가격에서 할인 금액을 뺀다. 그 결과가 음수라면 할인 후 메뉴 가격을 0으로 정한다. 배달비에는 할인이 적용되지 않는다. 따라서 실제 결제 금액은 할인 후 메뉴 가격에 해당 식당의 배달비를 더한 값이다. 쿠폰을 사용하지 않을 때에는 원래 메뉴 가격과 배달비를 더한다. 사용자는 실제 결제 금액이 가장 작은 주문 방법을 고르려 한다. 결제 금액이 같은 방법이 여러 개라면 식당 번호가 작은 방법을 고른다. 식당 번호까지 같으면 쿠폰 번호가 작은 방법을 고르며, 쿠폰을 사용하지 않는 방법의 쿠폰 번호는 0으로 취급한다. 사용할 수 있는 쿠폰이 하나도 없어도 쿠폰 없이 주문할 수 있으므로 선택할 방법은 항상 존재한다. 이 규칙에 따라 결제 금액, 식당 번호, 쿠폰 번호를 구하는 프로그램을 작성한다.

입력

첫째 줄에 식당 수 N과 쿠폰 수 K가 공백으로 구분되어 주어진다.
다음 N개의 줄에 각 식당의 메뉴 가격 P와 배달비 F가 공백으로 구분되어 주어진다.
이어서 K개의 줄에 각 쿠폰의 최소 메뉴 금액 T와 할인 금액 D가 공백으로 구분되어 주어진다.
모든 수는 정수다. 1 ≤ N ≤ 10,000, 1 ≤ K ≤ 10, 1 ≤ P ≤ 100,000, 0 ≤ F ≤ 10,000, 1 ≤ T ≤ 100,000, 1 ≤ D ≤ 100,000이다. 서로 다른 식당이나 쿠폰의 정보가 같을 수도 있다.

출력

선택한 방법의 실제 결제 금액, 식당 번호, 쿠폰 번호를 이 순서대로 한 줄에 공백으로 구분하여 출력한다. 쿠폰을 사용하지 않으면 쿠폰 번호로 0을 출력한다.

3 2
12000 2000
9500 1000
15000 0
10000 4000
9000 2000

8500 2 2

2 2
3000 500
4000 500
3000 5000
3000 6000

500 1 1

2 1
4200 800
5000 0
6000 2000

5000 1 0

출처: Devin.KR 자체 제작