I'm sorry to ask a foolish problem about my submission.So I share a way to solve 808E by ternary searching.

As we can see, *W*[*i*] = 1, 2, 3. We sort the Souvenirs which have the same *W*[*i*] by their *C*[*i*]. Then we know we will just choose a prefix for each *W*[*i*].

If we get X Souvenirs that *W*[*i*] = 3,we remain (*m* - 3*X*) to get Souvenirs that *W*[*i*] = 1, 2. Let's define *F*[*i*][*x*] the prefix sum of Souvenirs that *W*[*i*] = *x*. If we get Y Souvenirs that *W*[*i*] = 2,our cost is *F*[*X*][3] + *F*[*Y*][2] + *F*[*m* - 3*X* - 2*Y*][1] (m-3X-2Y>=0).

We can try every X and use ternary searching to find the best Y.The complexity is *O*(*nlogn*).

My submission:http://codeforces.com/contest/808/submission/27174539