appendとリスト結合の実行時間の差

事の発端

友人とatcoderの問題を解いてる時に、
https://atcoder.jp/contests/abc121/tasks/abc121_c

N,M = [int(s) for s in input().split()]
lst=[]
for i in range(N):
  lst.append([int(s) for s in input().split()])
lst.sort()
count=0
cost=0
for e in lst:
  count+=e[1]
  cost+=e[0]*e[1]
  if(count>=M):
    cost-=e[0]*(count-M)
    break
print(cost)

は通るんですが、

N,M = [int(s) for s in input().split()]
lst=[]
for i in range(N):
  lst = lst + [[int(s) for s in input().split()]]
lst.sort()
count=0
cost=0
for e in lst:
  count+=e[1]
  cost+=e[0]*e[1]
  if(count>=M):
    cost-=e[0]*(count-M)
    break
print(cost)

はTLEで通らなかった。

配列の生成は重そうなイメージあったんですが、実感したことはなかったので下記で確認。

import time
n = 100000
ex_1 = []
ex_2 = []

start_1 = time.time()
for i in range(n):
    ex_1 = ex_1 + [i]
end_1 = time.time()

start_2 = time.time()
for i in range(n):
    ex_2.append(i)
end_2 = time.time()

print("結合time = {}".format(end_1 - start_1))
# 結合time = 17.951491832733154
print("append time = {}".format(end_2 - start_2))
# append time = 0.015935897827148438

3桁くらいの差がありました。
リストの結合は安直に使わないほうが良さそうでした。