The term of this problem is the same as the previous one, the only exception — increased restrictions.
The first line contains two positive integers *n* and *k* (1 ≤ *n* ≤ 100 000, 1 ≤ *k* ≤ 10<sup class="upper-index">9</sup>) — the number of ingredients and the number of grams of the magic powder.

The second line contains the sequence *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> (1 ≤ *a*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">9</sup>), where the *i*-th number is equal to the number of grams of the *i*-th ingredient, needed to bake one cookie.

The third line contains the sequence *b*<sub class="lower-index">1</sub>, *b*<sub class="lower-index">2</sub>, ..., *b*<sub class="lower-index">*n*</sub> (1 ≤ *b*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">9</sup>), where the *i*-th number is equal to the number of grams of the *i*-th ingredient, which Apollinaria has.
none
1 1000000000
1
1000000000
2000000000
10 1
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
1 1 1 1 1 1 1 1 1 1
0
3 1
2 1 4
11 3 16
4
4 3
4 3 5 6
11 12 14 20
3
10 926
5 6 8 1 2 5 1 8 4 4
351 739 998 725 953 970 906 691 707 1000
137
20 925
7 3 1 2 1 3 1 3 1 2 3 1 5 8 1 3 7 3 4 2
837 898 965 807 786 670 626 873 968 745 878 359 760 781 829 882 777 740 907 779
150
30 300
1 4 2 1 2 5 6 4 1 3 2 1 1 1 1 1 2 3 1 3 4 2 2 3 2 2 2 1 1 1
997 817 767 860 835 809 817 565 630 804 586 953 977 356 905 890 958 916 740 583 902 945 313 956 871 729 976 707 516 788
164
40 538
1 3 3 1 4 1 1 1 1 5 3 3 4 1 4 2 7 1 4 1 1 2 2 1 1 1 1 4 1 4 2 3 3 3 1 3 4 1 3 5
975 635 795 835 982 965 639 787 688 796 988 779 839 942 491 696 396 995 718 810 796 879 957 783 844 765 968 783 647 214 995 868 318 453 989 889 504 962 945 925
104
1 1
1000000000
1000000000
1
50 530
2 3 3 1 1 1 3 4 4 2 4 2 5 1 3 1 2 6 1 1 2 5 3 2 1 5 1 3 3 2 1 1 1 1 2 1 1 2 2 1 4 2 1 3 1 2 1 1 4 2
959 972 201 990 675 679 972 268 976 886 488 924 795 959 647 994 969 862 898 646 763 797 978 763 995 641 923 856 829 921 934 883 904 986 728 980 1000 775 716 745 833 832 999 651 571 626 827 456 636 795
133
60 735
3 1 4 7 1 7 3 1 1 5 4 7 3 3 3 2 5 3 1 2 3 6 1 1 1 1 1 2 5 3 2 1 3 5 2 1 2 2 2 2 1 3 3 3 6 4 3 5 1 3 2 2 1 3 1 1 1 7 1 2
596 968 975 493 665 571 598 834 948 941 737 649 923 848 950 907 929 865 227 836 956 796 861 801 746 667 539 807 405 355 501 879 994 890 573 848 597 873 130 985 924 426 999 550 586 924 601 807 994 878 410 817 922 898 982 525 611 685 806 847
103
70 130
2 1 2 2 3 3 2 5 2 2 3 3 3 1 1 4 3 5 3 2 1 3 7 1 2 7 5 2 1 6 3 4 1 2 1 1 1 1 3 6 4 2 2 8 2 2 4 1 4 2 1 4 4 3 5 1 1 1 1 1 2 3 1 5 1 3 3 4 2 2
473 311 758 768 797 572 656 898 991 534 989 702 934 767 777 799 1000 655 806 727 718 948 834 965 832 778 706 861 799 874 745 970 772 967 984 886 835 795 832 837 950 952 475 891 947 952 903 929 689 478 725 945 585 943 771 631 729 887 557 738 824 758 999 786 669 992 918 762 964 941
119
80 979
2 1 1 1 2 1 1 1 3 1 4 4 2 1 1 3 1 1 2 1 4 1 1 2 5 4 8 1 3 6 5 7 2 3 4 1 2 2 6 1 2 2 4 1 1 2 3 2 8 1 1 3 3 4 1 1 2 1 4 4 1 4 3 2 6 5 2 1 4 1 2 3 2 1 3 3 1 2 1 3
498 976 513 869 917 914 664 656 957 893 981 947 985 693 576 958 987 822 981 718 884 729 295 683 485 998 730 894 731 975 739 854 906 740 987 976 606 689 990 775 522 994 920 893 529 651 989 799 643 215 946 987 297 868 425 810 694 908 736 903 970 751 625 904 955 945 839 777 977 974 905 900 666 680 799 873 565 919 536 686
128
1 1000
1000
1000
2
1 1000
1
1000
2000
1 1
4
6
1
1 1
1
1
2
1 1
1000000000
1
0
1 1000000000
1000000000
1000000000
2
1 1000000000
100000000
1000000000
20
1 1000000000
654321
1000000000
3056
1 786543211
12345678
987654321
143
20 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
1
13 961166382
312 781 329 6 813 68 872 146 33 382 134 744 353
904116983 692808881 382512127 462746212 130261069 450407093 112139570 386577765 867425952 354457553 248439687 817592835 682387533
714283
1 1000000000
1
2
1000000002
6 1000000000
1 1 1 1 1 1
1000000000 1 1000000000 1000000000 1000000000 1000000000
1000000000
2 1000000000
1 1
1 1
500000001
1 1
10
2
0
2 1
2 2
1 1
0
2 1000000000
1 1
1000000000 1000000000
1500000000
2 6
1 3
6 2
2
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
l = 0
r = 10 ** 18
while r - l > 1:
    m = (l + r) // 2
    tek = 0
    for i in range(len(a)):
        tek += max(a[i] * m - b[i], 0)
    if tek >= k:
        r = m
    else:
        l = m
print(r)
