Stealing Snacks from Juniors

Interview

Time limit1sMemory limit256 MB

Summary
Choose a subset of snacks whose total fullness reaches M, minimizing total satisfaction, or report that it is impossible.
Level

Medium6 of 10

Topics
Dynamic programming, Greedy, Sorting
Solved
No attempts yet

Problem

Seungyeop is the most senior soldier in his unit, a sergeant one week away from discharge. Nobody on the base can stop him.

His hobby is opening his juniors' footlockers while they are out on work detail or guard duty and stealing their snacks.

Seungyeop has a fixed 'fullness threshold' MM, the amount of fullness at which he feels satisfied, and his goal is to feel MM worth of fullness by eating snacks. If he cannot reach at least MM fullness, he gets angry.

Wondering whose snacks to steal, he orders Hyeoncheol, his most docile junior, to bring him enough snacks to fill him up.

Hyeoncheol resents Seungyeop for bullying the other juniors, so he plans to pick only the snacks Seungyeop likes the least.

Seungyeop has rated how tasty every snack sold at the PX is, giving each a satisfaction score.

Help Hyeoncheol, who is suffering, and compute the minimum satisfaction Seungyeop can get while filling his stomach!

Input

The first line gives the number of juniors NN (1 ≤ NN ≤ 100) and Seungyeop's fullness threshold MM (1 ≤ MM ≤ 100,000), separated by a space.

The next NN lines each give the fullness WW (1 ≤ WW ≤ 1,000) and satisfaction HH (1 ≤ HH ≤ 1,000) obtained by stealing that junior's snack, separated by a space.

Output

On the first line, print the minimum satisfaction Seungyeop can get while reaching the fullness threshold.

If Seungyeop cannot reach the fullness threshold with snacks, print “죄송합니다 한승엽 병장님” on one line.

Examples2

  1. Example 1

    Input
    4 6
5 10
2 6
3 5
4 4
    Expected output
    9

  2. Example 2

    Input
    2 10
3 5
4 1
    Expected output
    죄송합니다 한승엽 병장님