Поиск оптимальной стоимости решения для коммивояжера

Я работаю над этой задачей:

TSP:
Input: A matrix of distances; a budget b
Output: A tour which passes through all the cities and has length <= b, 
if such a tour exists.

TSP-OPT
Input: A matrix of distances
Output: The shortest tour which passes through all the cities.

Покажите, что если TSP может быть решена за полиномиальное время, то и TSP-OPT может быть решена.

Теперь первое, что нужно сделать Имейте в виду, что если бы я знал стоимость оптимального решения, я бы просто установил b на это значение и вуаля. И, разве вы не знаете, в другом месте моей книги есть подсказка для этой самой проблемы:

Как нам найти оптимальную стоимость? Легко: бинарным поиском.

Думаю, я могу что-то неправильно понять здесь. Двоичный поиск предназначен для поиска позиции данного элемента в отсортированном списке. Как именно это могло помочь мне найти оптимальную стоимость? Я искренне сбит с толку. К сожалению, дальнейших подробностей авторы не уточняют.

Единственное, что я мог бы придумать, чтобы решить эту проблему, - это доказать, что они обе сводятся к другой NP-полной проблеме, что я могу в конечном итоге сделать, но все же ... это меня беспокоит.