길이가 N인 수열 A = {a1, a2, a3, ..., aN}는 초항이 a이고 공차가 d인 유한 등차수열이다.
양의 정수 M에 대하여 합이 M인 A의 부분 수열 중 가장 긴 것을 구하시오.
부분 수열이란 주어진 수열에서 원래 순서를 유지하며 0개 이상의 원소를 제거하여 얻은 수열이다.
첫째 줄에 네 정수 N, a, d, M이 공백으로 구분되어 주어진다. (1 ≤ N, a, d ≤ 106; 1 ≤ M ≤ 1018)
첫째 줄에 합이 M인 A의 부분 수열 중 가장 긴 것의 길이 L을 출력한다.
둘째 줄에 그러한 부분 수열의 원소 L개를 공백으로 구분하여 출력한다. 가능한 답이 여러 가지라면 그중 아무거나 출력한다.
만약 그런 부분 수열이 존재하지 않는다면 첫째 줄에 −1을 대신 출력한다.
5 2 2 10
2 4 6
3 1 2 7
-1
예제 입력 1에서 주어진 수열은 A = {2, 4, 6, 8, 10}이다. 길이 조건을 제외하면 가능한 B의 후보는 {10}, {2, 8}, {4, 6}이다. 이 중 길이가 가장 긴 수열은 {2, 8}과 {4, 6}이므로 둘 중 아무거나 출력하면 된다.
