Bessie is looking for a new job! Fortunately, K farmers are currently hiring and conducting interviews. Since jobs are highly competitive, the farmers have decided to number and interview cows in the order they applied. There are N cows that applied before Bessie, so her number is N+1(1≤K≤N≤3⋅105).
The interview process will go as follows. At time 0, farmer i will start interviewing cow i for each 1≤i≤K. Once a farmer finishes an interview, he will immediately begin interviewing the next cow in line. If multiple farmers finish at the same time, the next cow may choose to be interviewed by any of the available farmers, according to her preference.
For each 1≤i≤N, Bessie already knows that cow i's interview will take exactly ti minutes (1≤ti ≤109). However, she doesn't know each cow's preference of farmers.
Since this job is very important to Bessie, she wants to carefully prepare for her interview. To do this, she needs to know when she will be interviewed and which farmers could potentially interview her. Help her find this information!
INPUT FORMAT (input arrives from the terminal / stdin):
The first line of the input will contain two integers N and K.
The second line will contain Nintegers t1…tN.
OUTPUT FORMAT (print output to the terminal / stdout):
On the first line, print the time Bessie's interview will begin.
On the second line, a bit string of length K, where the i-th bit is 1if farmer i could interview Bessie and 0 otherwise.
SAMPLE INPUT:
6 3
3 1 4159 2 6 5
SAMPLE OUTPUT:
8
110
There are 6 cows aside from Bessie and 3 farmers, and the interview process will go as follows:
1.At time t=0, farmer 1 interviews cow 1, farmer 2 interviews cow 2, and farmer 3 interviews cow 3.
2.At time t=1, farmer 2 finishes his interview with cow 2 and starts interviewing cow 4.
3.At time t=3, both farmer 1 and farmer 2 finish their interviews, and there are two possibilities:
Farmer 1 interviews cow 5 and farmer 2 interviews cow 6. In this case, farmer 2 would finish his interview at time t=8 and start interviewing Bessie.
Farmer 1 interviews cow 6 and farmer 2 interviews cow 5. In this case, farmer 1 would finish his interview at time t=8 and start interviewing Bessie.
Thus, Bessie's interview will begin at time t=8, and she could be interviewed by either farmer 1 or farmer 2.
SCORING:
Inputs 2-3: No two farmers finish at the same time.
Inputs 4-9: N≤3⋅103
Inputs 10-21: No additional constraints.
Problem credits: Avnith Vijayram
扫码领取USACO试题答案+详细解析
咨询一对一备赛规划
