Card Game Strategy

Time Limit : 5 sec, Memory Limit : 1048576 KB

Problem B Card Game Strategy

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:

  1. Alice chooses an integer between $a$ and $b$, inclusive. Call this integer $t$. Alice then tells Bob the value of $t$.
  2. 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$.

Input

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.

Output

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.

Sample Input 1

4 2 58 100
10 10 50 80

Output for the Sample Input 1

75
2 3

Sample Input 2

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

Output for the Sample Input 2

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/