Вы участвуете в турнире под названием «Очередной Турнир». В турнире участвуют \(n + 1\) человек: вы и \(n\) ваших соперников, пронумерованных от \(1\) по \(n\).
Каждый участник сыграет против каждого ровно один раз. Если соперник \(i\) состязается с соперником \(j\), он выигрывает тогда и только тогда, когда \(i > j\).
Если же оппонент \(i\) играет против вас, все становится немного сложнее. Для того чтобы победить оппонента \(i\), вам нужно готовиться к матчу на протяжении \(a_i\) минут. В противном случае вы проиграете данному сопернику.
У вас есть \(m\) свободных минут для подготовки к матчам, но вы можете готовиться одновременно только к одному матчу. Другими словами, если вы хотите выиграть у оппонентов \(p_1, p_2, \dots, p_k\), вы должны потратить на подготовку \(a_{p_1} + a_{p_2} + \dots + a_{p_k}\) минут. Если же это число больше \(m\), вы не сможете их всех победить.
Финальное место каждого участника равно количеству участников со строго большим количеством побед \(+\) \(1\). Например, если \(3\) участника выиграли по \(5\) раз, \(1\) участник — \(3\) раза, и \(2\) участника — по \(1\) разу, то первые \(3\) займут \(1\)-е место, четвертый — \(4\)-е место, и два последних — \(5\)-е место.
Посчитайте минимально возможное место (меньше — лучше), которое вы сможете занять, если на подготовку к матчам у вас всего \(m\) минут.
Выходные данные
Для каждого набора входных данных выведите наименьшее возможное место, которое вы сможете занять, если на подготовку у вас есть только \(m\) минут.
Примечание
В первом наборе входных данных у вас есть время на подготовку ко всем оппонентам, а потому вы выиграете все \(4\) матча и займете \(1\)-е место, так как все ваши оппоненты выиграют не более \(3\) матчей.
Во втором наборе вы можете подготовиться ко второму оппоненту и выиграть у него. В результате вы выиграете \(1\) матч, оппонент \(1\) — \(1\) матч, оппонент \(2\) — \(1\) матч, оппонент \(3\) — \(3\) матча. А потому оппонент \(3\) займет \(1\)-е место, и все остальные, включая вас, — \(2\)-е место.
В третьем наборе входных у вас нет времени на подготовку, а потому вы проиграете все матчи. Так как у каждого из оппонентов будет хотя бы \(1\) победа, вы займете последнее место (место \(6\)).
В четвертом наборе у вас нет времени на подготовку, но вы все равно выиграете у первого оппонента. В результате оппонент \(1\) не выиграл ни одного матча, у вас \(1\) победа, и у всех остальных хотя бы \(2\) победы. А потому ваше место \(4\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
4 401
100 100 200 1
3 2
1 2 3
5 0
1 1 1 1 1
4 0
0 1 1 1
4 4
1 2 2 1
|
1
2
6
4
1
|