Problem 42834. Integer complexity (Large numbers)

Inspired by Problem 42831, this problem aims to calculate the integer complexity for large numbers. The integer complexity of a natural number n is defined as the least number of 1’s required to express n using only the two operations + and × and parentheses.

Example: the number 11 may be represented using 8 ones:

    11 = (1 + 1 + 1) × (1 + 1 + 1) + 1 + 1.

However, it has no representation using 7 or fewer ones. Therefore, its complexity is 8.

Your solution will be scored based on its running time. No cheating please.