計算量のlogCの出どころを知りたい。

前提

下記に示すプログラムの計算量を知りたいです。
解答では、（NlogNlogC）となっています。
NlogNまでは、二分探索とソートの処理というめぼしはつくのですが、logCの行方がわからず困っております。

該当のソースコード

C++

#include <iostream>#include <vector>#include <algorithm>using namespace std; int main() { long long N, K; cin >> N >> K; vector<long long> a(N), b(N); for (int i = 0; i < N; ++i) cin >> a[i]; for (int i = 0; i < N; ++i) cin >> b[i]; // b はあらかじめソートしておく sort(b.begin(), b.end()); // 判定問題 auto check = [&](long long x) -> bool { long long cnt = 0; for (int i = 0; i < N; ++i) { cnt += upper_bound(b.begin(), b.end(), x / a[i]) - b.begin(); } return (cnt >= K); }; // 二分探索 (right は十分大きな値に設定) long long left = 0, right = 1LL<<60; while (right - left > 1) { long long mid = (left + right) / 2; if (check(mid)) right = mid; else left = mid; } cout << right << endl;}

試したこと

再度ひとつずつ、計算量を見てみるも、N、logNしか見当たらずでした。

補足情報（FW/ツールのバージョンなど）

解説には最大値とありますが、そもそもプログラム内にmax関数なんて使っていないような気がしています...
参考にした解説ページ
リンクに飛べます。