Alice and Bob are going to play a card game. There are $n$ cards, each having an integer written on it. The game proceeds as follows:

- Alice chooses an integer between $a$ and $b$, inclusive. Call this integer $t$. Alice then tells Bob the value of $t$.
- Bob chooses $k$ out of the $n$ cards. Compute the sum of the integers written on the $k$ cards Bob chooses. Call this sum $u$.

Alice's objective is to make $|t - u|$ as large as possible and Bob's is to make $|t - u|$ as small as possible.

Prior to the game, both Alice and Bob know the values of $n$, $k$, $a$, and $b$, and also the integers on the cards. Both Alice and Bob will play optimally. In particular, Alice will make a choice, knowing that Bob will surely minimize $|t - u|$ for told $t$. Additionally, assume that Alice prefers to choose smaller $t$ if she has multiple equally good choices.

Your task is to determine the outcome of the game: the value of $t$ Alice will choose and the $k$ cards Bob will choose for that $t$.

The input consists of two lines representing a single test case. The first line contains four integers $n$, $k$, $a$, and $b$ $(1 \leq k \leq n \leq 600, 0 \leq a \leq b \leq 180,000)$. The second line contains $n$ integers $x_1, ..., x_n$ $(0 \leq x_i \leq 300)$, denoting that $x_i$ is written on the $i$-th card.

Display two lines: The first line should contain an integer representing the value of $t$ Alice will choose. The second line should contain k distinct integers between 1 and $n$, inclusive, representing the indices of the cards Bob will choose. If Bob has multiple equally good choices, display any one of them.

4 2 58 100 10 10 50 80

75 2 3

8 3 1300 1800 2 0 1 5 0 4 1 9

1800 4 6 8

Source: Japan Alumni Group Spring Contest 2015
, Japan, 2015-04-19

http://acm-icpc.aitea.net/

http://jag2015spring.contest.atcoder.jp/

http://acm-icpc.aitea.net/

http://jag2015spring.contest.atcoder.jp/