18233번 - 러버덕을 사랑하는 모임 스페셜 저지

다영이는 얼마 전에 러버덕을 사랑하는 모임(이하 러사모)에 가입했다. 다영이는 E개의 러버덕 인형을 가지고 있는데, 가입 기념으로 러사모 회원들에게 러버덕 인형을 선물하려고 한다.

러사모 회장에게 의뢰하여 조사해본 결과 러사모 회원은 다영이를 제외하고 N명이 있고, 각 러사모 회원 i는 x_i개 이상 y_i개 이하의 인형만 받는다고 한다. 다영이는 러버덕 인형을 선물 받는 것에 조건을 붙이는 러사모 회원들이 괘씸해서 정확히 P명에게 주는 러버덕 인형들의 합이 E개인 경우에만 인형을 선물하려고 한다. 과연 다영이는 인형을 선물할 수 있을까?

첫 번째 줄에 정수 N, P, E가 공백으로 구분되어 주어진다. (1 ≤ N, P ≤ 20, 1 ≤ E ≤ 1,000,000)

그 다음 줄부터 N개의 줄에 걸쳐 회원 1부터 순서대로 x_i와 y_i가 공백으로 구분되어 주어진다. (1 ≤ x_i ≤ y_i ≤ 1,000,000)

다영이가 인형을 선물할 수 있다면 첫 번째 줄에 회원 i에게 선물할 인형 개수를 회원 1부터 N까지 순서대로 공백으로 구분하여 출력한다. 가능한 경우가 여러 개라면 그중 하나를 출력한다.

어떠한 경우로도 인형을 선물할 수 없다면 -1을 출력한다.