항공권 달력의 두 날짜

문제

여행자는 한 도시로 갔다가 원래 도시로 돌아오는 왕복 여행을 계획하고 있다. 항공권 달력에는 연속한 N일에 대하여 가는 편과 돌아오는 편의 가격이 각각 적혀 있다. 날짜는 실제 월이나 요일 대신 1일부터 N일까지의 정수 번호로 표시한다. 같은 날짜에 여러 항공편이 있는 경우에도 달력에는 이미 그날 이용할 수 있는 가장 저렴한 항공권의 가격 하나만 적혀 있다. 가는 날짜를 i, 돌아오는 날짜를 j라고 하자. 여행자가 목적지에서 보내는 기간은 j-i일로 계산한다. 여행자는 이 기간이 L일 이상 U일 이하이기를 원한다. L은 1 이상이므로 돌아오는 날짜는 항상 가는 날짜보다 늦어야 한다. 달력 밖의 날짜는 선택할 수 없으며, 가는 편 항공권 하나와 돌아오는 편 항공권 하나를 각각 구매해야 한다. 달력에서 가격이 0인 것은 무료 항공권을 뜻하지 않는다. 해당 날짜에 그 방향으로 이용할 수 있는 항공권이 없다는 뜻이다. 따라서 선택한 두 날짜에서는 각 방향의 가격이 모두 양수여야 한다. 왕복 항공권의 총가격은 선택한 가는 편 가격과 돌아오는 편 가격의 합이다. 별도의 할인이나 추가 요금은 없다. 여행자는 기간 조건을 만족하는 선택 중 총가격이 가장 작은 것을 원한다. 총가격이 같은 선택이 여러 개라면 가는 날짜 i가 작은 것을 선택한다. 가는 날짜까지 같다면 돌아오는 날짜 j가 작은 것을 선택한다. 두 방향에 모두 항공권이 있더라도 기간 조건을 만족하는 날짜 조합이 없을 수 있다. 달력에 적힌 정보를 이용하여 선택할 총가격과 두 날짜를 구하고, 여행 자체가 불가능하면 그 사실을 출력하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N, L, U가 공백으로 구분되어 주어진다. 2 ≤ N ≤ 365이고, 1 ≤ L ≤ U ≤ N-1이다.
둘째 줄에 날짜순으로 가는 편 가격 A_1, …, A_N이 주어진다.
셋째 줄에 날짜순으로 돌아오는 편 가격 B_1, …, B_N이 주어진다.
모든 가격은 정수이며 0 ≤ A_i, B_i ≤ 1,000,000이다. 가격 0은 해당 방향의 항공권이 없음을 나타낸다.

출력

조건을 만족하는 선택이 있으면 최소 총가격, 가는 날짜 i, 돌아오는 날짜 j를 공백으로 구분하여 한 줄에 출력한다. 날짜는 1부터 센다. 동점이면 i가 작은 선택을, i도 같으면 j가 작은 선택을 출력한다. 조건을 만족하는 선택이 없으면 -1만 출력한다.

5 1 2
70 40 0 30 90
0 60 20 20 10

40 4 5

4 1 2
10 10 0 0
0 5 5 5

15 1 2

3 2 2
0 20 30
40 50 60

-1

출처: Devin.KR 자체 제작