Tərəvəzlərin bişirilməsi

Tərəvəz bişirməyin sirri, bütün parçaların təxminən eyni ölçüdə olmasındadır. Əks halda, kiçik parçalar çox bişər, böyük parçalar isə az bişər. Xoşbəxtlikdən, mətbəx bıçağından istifadə etməyi bilirsiniz, amma valideynlərinizin iti alətlərdən istifadə ilə bağlı xəbərdarlıqları hələ də yadınızdadır. Buna görə də, bıçağı mümkün qədər az istifadə etmək istəyirsiniz. Siz $w$ ağırlığında bir tərəvəz parçasını istənilən şəkildə $w_{left}$ və $w_{right}$ ağırlıqlarına malik iki hissəyə bölə bilərsiniz, burada $w_{left}+w_{right}=w$. Bu əməliyyatı "kəsmə" adlandıraq.

Mövcud tərəvəz parçalarının ölçülərini bilmək şərti ilə, ən kiçik və ən böyük parça arasındakı nisbətin verilmiş həddən böyük olacağı qədər kəsiklərin minimal sayını müəyyən edin.

Giriş verilənləri

Əvvəlcə $t(0.5<t<1)$ ondalık sayı və təbii $n(n\le 1000)$ sayı verilir. Sonra $n$ müsbət tam ədədlər $w_1,w_2,...,w_n$ gəlir. Bütün ağırlıqlar $10^6$-dan kiçikdir.

Çıxış verilənləri

Ən kiçik və ən böyük parça arasındakı nisbətin $t$-dən böyük olacağı qədər kəsiklərin minimal sayını çıxarın. Lazımi kəsiklərin sayının $500$-dən az olduğunu düşünün. Ondalık ədədlərlə bağlı problemlərdən qaçmaq üçün, $t$ nisbəti üçün optimal cavabın $t+0.0001$ nisbəti üçün də eyni olacağını fərz edin.

Nümunələr