Jest n pudełek z bombkami. Każde ma swoją wagę oraz wytrzymałość, czyli jaki maksymalny ciężar można postawić na górze pudełka. Chcemy zbudować jak najwyższą piramidę z pudełek tak, by żadne pudełko się nie zawaliło. Pudełka możemy tylko stawiać jedno na drugim.
W pierwszej linii wejścia jest jedna liczba n, 1 <= n <= 1000, równa liczbie pudełek z bombkami. Kolejne n wierszy opisuje pudełka. W każdym wierszu są dwie liczby W i w, 1 <= W,w <= 2 000 000, oznaczające odpowiednio wytrzymałość i wagę kolejnego pudełka. Twój program powinien wypisać jedną liczbę - ile maksymalnie pudełek można na sobie poustawiać, by nie było katastrofy.
Dla danych wejściowych:
7 1 3 3 4 2 3 5 6 3 5 8 7 4 6
Prawidłową odpowiedzią jest:
3
[Zgłoś rozwiązanie] [Moje zgłoszenia]